Заполнено ячеек
Сравнения
Самая длинная пока

  • Заполняется
  • Читается
  • Ответ

Подробнее о наибольшей возрастающей подпоследовательности

Наибольшая возрастающая подпоследовательность (LIS)

Сколько чисел из списка можно выбрать, сохраняя их порядок, так, чтобы каждое было больше предыдущего? Ответ на этот вопрос дает наибольшая возрастающая подпоследовательность. Введите список и посмотрите, как динамическое программирование находит для каждой позиции самую длинную цепочку, которая в ней заканчивается. Нажмите Пуск, чтобы посмотреть, как заполняется таблица, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Введите список чисел. Для каждой позиции таблица хранит длину самой длинной возрастающей цепочки значений, которая в ней заканчивается, и предыдущую позицию, которую эта цепочка продолжает. Отметьте «Разрешить равные значения», чтобы искать цепочки, которые никогда не убывают. В конце цепочка восстанавливается от ее последнего значения назад. Кнопка Новый пример создает другой список. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.

Как это работает

  1. Введите список чисел через запятую или пробел. Отметьте «Разрешить равные значения», чтобы искать цепочки, которые никогда не убывают.
  2. Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место.
  3. Посмотрите, как каждая позиция сравнивается со всеми предыдущими, а затем как самая длинная цепочка восстанавливается оранжевым цветом.

Как устроена таблица

В таблице три строки: значения, длина наибольшей возрастающей подпоследовательности, которая заканчивается в каждой позиции, и позиция, которую она продолжает. Одно значение само по себе — цепочка длины 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 в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор