Алгоритмы
LIS: Longest Increasing Subsequence
Цели урока
- Понимать задачу LIS
- Реализовать O(n²) DP решение
- Реализовать O(n log n) решение с бинарным поиском
- Восстанавливать саму LIS
- Решать вариации: non-decreasing, количество LIS
Предварительные знания
- Динамическое программирование
- Бинарный поиск
LIS - одна из самых компактных задач DP. O(n²) решение понятно, но O(n log n) через бинарный поиск - произведение искусства. Эта задача - частый гость на собеседованиях в Google и Facebook.
- Patience sorting: карточная игра = LIS
- Биоинформатика: выравнивание генов
- Планирование: упорядочивание зависимых задач
- Сжатие данных: поиск закономерностей
От карточной игры к соответствию Робинсона-Шенстеда
Наибольшая возрастающая подпоследовательность стоит на стыке алгоритмов и чистой комбинаторики. Гилберт де Борегар Робинсон описал нужную конструкцию в 1938 году, а Крейг Шенстед в 1961 году переосмыслил её как процедуру вставки и получил то, что сейчас называют соответствием Робинсона-Шенстеда между перестановками и парами таблиц Юнга. Длина первой строки полученной таблицы равна длине LIS, и этот факт полностью уточнил Кёртис Грин в 1974 году. Тот же процесс вставки, это в точности patience sorting, раскладывание карт по стопкам по простому правилу, и именно поэтому практичный алгоритм за O(n log n) заменяет наивную динамику за O(n в квадрате). Майкл Фредман проанализировал оценку n log n в 1975 году. Так что массив верхушек стопок, поддерживаемый бинарным поиском, прямой потомок карточной игры и куска теории представлений.
Что такое LIS?
**LIS (Longest Increasing Subsequence)** - самая длинная подпоследовательность, в которой каждый следующий элемент строго больше предыдущего.
**Применения:** планирование задач, box stacking, Russian doll envelopes, patience sorting.
arr = [3, 1, 4, 1, 5, 9, 2, 6]. Длина LIS?
DP решение O(n^2)
**dp[i]** = длина LIS, заканчивающейся на элементе arr[i].
Почему dp[i] инициализируется единицей?
O(n log n) через бинарный поиск
**Гениальная идея:** поддерживаем массив tails, где tails[i] - минимальный последний элемент LIS длины i+1.
**Важно:** tails - НЕ сама LIS! Это вспомогательный массив. [2, 3, 7, 18] - не обязательно подпоследовательность исходного массива.
Почему мы заменяем элемент в tails, а не добавляем новый?
Восстановление LIS
**Чтобы восстановить саму LIS, храним дополнительную информацию.**
Что хранит массив parent в алгоритме восстановления?
Вариации LIS
**Несколько популярных вариаций задачи:**
**Паттерн:** многие 2D задачи сводятся к LIS после умной сортировки по одному измерению.
Чем отличается bisect_left от bisect_right для LIS?
LIS
- LIS, это возрастающая подпоследовательность максимальной длины
- O(n²) DP: dp[i] = max(dp[j]+1) для arr[j] < arr[i]
- O(n log n): массив tails + бинарный поиск
- tails[i], это минимальный конец LIS длины i+1
- bisect_left для <, bisect_right для ≤
Связанные темы
LIS связана с другими классическими задачами DP.
- LCS — LIS(A) = LCS(A, sorted(A))
- DP основы — Базовая парадигма
- Бинарный поиск — Для O(n log n) решения
Связанные уроки
- alg-21-dp — O(n^2) LIS - 1D-рекуррентность динамического программирования
- alg-10-binary-search — O(n log n) LIS вставляет элементы бинарным поиском
- alg-28-lcs — LIS равен LCS с отсортированным массивом
- dm-09 — Теорема Дилворта связывает LIS с разбиением на антицепи
- ml-01-intro