- Заполняется
- Читается
- Ответ
Наибольшая возрастающая подпоследовательность (LIS)
Сколько чисел из списка можно выбрать, сохраняя их порядок, так, чтобы каждое было больше предыдущего? Ответ на этот вопрос дает наибольшая возрастающая подпоследовательность. Введите список и посмотрите, как динамическое программирование находит для каждой позиции самую длинную цепочку, которая в ней заканчивается. Нажмите Пуск, чтобы посмотреть, как заполняется таблица, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Введите список чисел. Для каждой позиции таблица хранит длину самой длинной возрастающей цепочки значений, которая в ней заканчивается, и предыдущую позицию, которую эта цепочка продолжает. Отметьте «Разрешить равные значения», чтобы искать цепочки, которые никогда не убывают. В конце цепочка восстанавливается от ее последнего значения назад. Кнопка Новый пример создает другой список. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.
Как это работает
- Введите список чисел через запятую или пробел. Отметьте «Разрешить равные значения», чтобы искать цепочки, которые никогда не убывают.
- Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место.
- Посмотрите, как каждая позиция сравнивается со всеми предыдущими, а затем как самая длинная цепочка восстанавливается оранжевым цветом.
Как устроена таблица
В таблице три строки: значения, длина наибольшей возрастающей подпоследовательности, которая заканчивается в каждой позиции, и позиция, которую она продолжает. Одно значение само по себе — цепочка длины 1. Затем проверяется каждая более ранняя позиция: если ее значение меньше, цепочку, которая там заканчивается, можно продолжить этим значением, и ее длина вырастет на единицу. Побеждает самое длинное такое продолжение, и его позиция записывается в третью строку.
Восстановление цепочки
Наибольшая возрастающая подпоследовательность заканчивается в позиции с наибольшей длиной. Оттуда третья строка показывает, какая позиция стоит перед ней, третья строка той позиции — какая стоит перед ней, и так далее, пока не встретится позиция без предшественника. Эти значения, прочитанные по порядку, и есть ответ. Если отмечено «Разрешить равные значения», значение может идти и после равного ему, и тогда получается самая длинная неубывающая цепочка.
Часто задаваемые вопросы
Чем подпоследовательность отличается от подмассива?
Подмассив — это блок соседних значений. Подпоследовательность сохраняет порядок, но может пропускать значения, поэтому в 3, 10, 2, 1, 20 значения 3, 10 и 20 образуют возрастающую подпоследовательность, хотя между ними стоят 2 и 1.
Насколько быстр алгоритм LIS?
Табличный метод сравнивает каждую пару позиций: n·(n − 1)/2 сравнений для n значений. Сортировка пасьянсом справляется за O(n log n): для каждой длины она хранит наименьшее значение, которым заканчивается цепочка этой длины, и ставит каждое новое значение на место двоичным поиском.
Единственна ли наибольшая возрастающая подпоследовательность?
Не всегда. В 1, 3, 2, 4 и 1, 3, 4, и 1, 2, 4 имеют длину 3. Таблица дает длину, а восстановление находит одну из них.
Где используется наибольшая возрастающая подпоследовательность?
При сравнении файлов и геномов, где некоторые методы сначала находят совпадающие строки, а затем берут возрастающую подпоследовательность их позиций; в задачах планирования и головоломках об укладке коробок в стопку; и в математике, где длина НВП случайной перестановки — знаменитый предмет изучения.
Отправляются ли куда-нибудь данные?
Нет. Все вычисляется в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор