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

Выбирайте числа из списка слева направо, каждое больше предыдущего. Насколько длинной может получиться такая цепочка? Вопрос достаточно прост для сборника головоломок, а ответ на него связывает карточный пасьянс, классическую таблицу динамического программирования и один из самых красивых результатов о случайных перестановках.

Ряд столбиков разной высоты, среди которых оранжевым выделена цепочка, поднимающаяся слева направо
Ряд столбиков разной высоты, среди которых оранжевым выделена цепочка, поднимающаяся слева направо

Задача

Дан список чисел. Подпоследовательность оставляет некоторые из них в исходном порядке. Она возрастающая, если каждое значение больше предыдущего. Наибольшая возрастающая подпоследовательность, или LIS, — самый длинный такой выбор. У списка из n значений 2ⁿ подпоследовательностей, поэтому перебрать их все можно только для очень коротких списков.

Таблица

Пусть len[i] — длина наибольшей возрастающей подпоследовательности, которая заканчивается ровно в позиции i. Она равна 1 для одного значения или 1 + len[j] для более ранней позиции j с меньшим значением — смотря что больше. Каждая позиция просматривает все более ранние, поэтому таблице нужно n·(n − 1)/2 сравнений. Ответ — наибольшее len[i], а если запоминать, какое j дало каждое len[i], можно восстановить саму подпоследовательность.

Пример

Возьмем 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. По позициям длины равны 1, 2, 1, 1, 3, 2, 3, 4, 3 и 5: 20 продолжает 3, 10; 4 продолжает 3; 6 продолжает 4, 7 — 6, а 9 — 7. Восстановление от 9 дает 3, 4, 6, 7, 9 — возрастающую подпоследовательность длины 5.

Быстрее: сортировка пасьянсом

Раскладывайте значения, как карты, по стопкам: каждое значение кладется на самую левую стопку, верхняя карта которой не меньше его, или начинает новую стопку справа. Число стопок равно длине LIS. Поскольку верхние карты стопок всегда упорядочены, нужную стопку можно найти двоичным поиском, и весь метод занимает O(n log n) шагов. Он назван в честь пасьянса, на который похож.

Немного математики

В 1935 году Пал Эрдёш и Джордж Секереш доказали, что в любом списке из n² + 1 различных чисел есть возрастающая или убывающая подпоследовательность длины n + 1. В 1961 году Станислав Улам спросил, какова длина LIS случайной перестановки n чисел. Ответ — около 2√n при больших n — получили в 1977 году Анатолий Вершик и Сергей Керов, а также Бен Логан и Ларри Шепп. В 1999 году Джинхо Байк, Перси Дейфт и Курт Йоханссон нашли точную форму ее колебаний: это распределение Трейси — Видома из теории случайных матриц.

Пал Эрдёш на студенческом семинаре в Будапеште в 1992 году. В 1935 году он и Дьёрдь Секереш доказали, что в любом списке из n² + 1 различных чисел есть возрастающая или убывающая подпоследовательность длины n + 1.
Пал Эрдёш на студенческом семинаре в Будапеште в 1992 году. В 1935 году он и Дьёрдь Секереш доказали, что в любом списке из n² + 1 различных чисел есть возрастающая или убывающая подпоследовательность длины n + 1.
Портрет Станислава Улама
Портрет Станислава Улама

Попробуйте сами

Откройте приложение и нажмите Шаг. Оранжевый столбец — позиция, которая сейчас вычисляется, а синий — более ранняя позиция, с которой ее сравнивают. Строка «Длина» растет по мере того, как находятся более длинные цепочки, строка «Идет после» запоминает, откуда они пришли, а в конце ответ восстанавливается оранжевым и показывается под таблицей.

Часто задаваемые вопросы

Какова временная сложность LIS?

O(n²) с таблицей, потому что каждая позиция просматривает все более ранние, и O(n log n) с сортировкой пасьянсом и двоичным поиском. Обоим способам нужно O(n) памяти.

Как найти наибольшую неубывающую подпоследовательность?

Разрешите значению идти после равного: сравнивайте с помощью ≤ вместо <. В приложении отметьте «Разрешить равные значения». В сортировке пасьянсом кладите каждое значение на самую левую стопку, верхняя карта которой строго больше его.

Что такое наибольшая убывающая подпоследовательность?

Это та же задача с обратным сравнением, или LIS списка, в котором у каждого значения изменен знак. По теореме Эрдёша — Секереша в достаточно длинном списке всегда есть длинная возрастающая или длинная убывающая подпоследовательность.

Какова длина LIS случайного списка?

Для случайной перестановки n различных чисел — около 2√n при больших n. Поправка растет как корень шестой степени из n, поэтому для тысячи чисел среднее около 58, чуть меньше, чем 2√1000 ≈ 63.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

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