ДП на подпоследовательностях: LIS и LCS

Два знаковых ДП о подпоследовательностях: самая длинная возрастающая в одном массиве и самая длинная общая для двух строк.

Подпоследовательность — то, что получается из последовательности удалением некоторых элементов без изменения порядка оставшихся (в отличие от подотрезка, элементы не обязаны идти подряд).

Зачем это нужно

LIS (Longest Increasing Subsequence) и LCS (Longest Common Subsequence) — два самых известных ДП на подпоследовательностях, и оба регулярно появляются на олимпиадах. LIS лежит в основе задач о «росте», расстановках, разбиениях на возрастающие цепочки. LCS — это база для сравнения строк, диффа файлов, биоинформатики (сравнение ДНК). Помимо практической пользы, эти задачи учат двум разным техникам: LIS показывает неочевидную оптимизацию до O(n log n) через бинпоиск, а LCS — классическое двумерное ДП по двум строкам.

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

Дан массив; нужно найти длину самой длинной строго возрастающей подпоследовательности. Например, в [10, 9, 2, 5, 3, 7, 101, 18] это [2, 3, 7, 18] или [2, 5, 7, 101] — длина 4.

Простое ДП за O(n^2): dp[i] — длина LIS, оканчивающейся в позиции i; для каждого i смотрим все j < i с a[j] < a[i]. Но есть элегантный приём за O(n log n). Идея: поддерживаем массив tails, где tails[k] — наименьший возможный последний элемент возрастающей подпоследовательности длины k+1. Для нового элемента бинпоиском находим место и обновляем.

from bisect import bisect_left

a = [10, 9, 2, 5, 3, 7, 101, 18]
tails = []                          # tails[k] = мин. хвост LIS длины k+1
for x in a:
    i = bisect_left(tails, x)       # куда встаёт x (строгое возрастание)
    if i == len(tails):
        tails.append(x)             # x продлевает самую длинную
    else:
        tails[i] = x                # x улучшает хвост длины i+1
print("Длина LIS:", len(tails))

Почему это работает? Длина tails в любой момент равна длине текущей LIS. Когда приходит x, мы либо удлиняем последовательность (если x больше всех хвостов), либо «улучшаем» хвост подходящей длины, делая будущее удлинение более вероятным. Каждый элемент — один бинпоиск O(log n), итого O(n log n). Заметь: сам tails — не LIS, но его длина верна.

Вывод:

Длина LIS: 4

LCS: наибольшая общая подпоследовательность

Даны две строки; нужно найти длину самой длинной подпоследовательности, общей для обеих. Для "AGGTAB" и "GXTXAYB" это "GTAB" — длина 4. Это классическое двумерное ДП.

Состояние dp[i][j] — длина LCS префиксов s[:i] и t[:j]. Переход:

Если s[i−1] == t[j−1] — символы совпали: dp[i][j] = dp[i−1][j−1] + 1 (берём этот символ в общую подпоследовательность).
Иначе берём лучшее, отбросив один символ: dp[i][j] = max(dp[i−1][j], dp[i][j−1]).

s, t = "AGGTAB", "GXTXAYB"
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if s[i - 1] == t[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

# Восстановление самой подпоследовательности по таблице:
i, j = m, n
res = []
while i > 0 and j > 0:
    if s[i - 1] == t[j - 1]:
        res.append(s[i - 1]); i -= 1; j -= 1
    elif dp[i - 1][j] >= dp[i][j - 1]:
        i -= 1
    else:
        j -= 1
print("Длина LCS:", dp[m][n], "| сама LCS:", "".join(reversed(res)))

Таблица заполняется по строкам; dp[m][n] — длина ответа. Чтобы вывести саму подпоследовательность, идём по таблице назад из правого нижнего угла: при совпадении символов берём его и шагаем по диагонали, иначе движемся туда, откуда пришёл максимум. Сложность — O(m·n) по времени и памяти.

Вывод:

Длина LCS: 4 | сама LCS: GTAB

Сравнение

Задача	Состояние	Сложность
LIS (наивно)	`dp[i]` — LIS, кончающаяся в i	`O(n^2)`
LIS (быстро)	массив хвостов + бинпоиск	`O(n log n)`
LCS	`dp[i][j]` по двум префиксам	`O(m·n)`

Подводные камни

Подпоследовательность ≠ подотрезок. Элементы не обязаны идти подряд — это частая путаница в формулировках.
Строгое или нестрогое возрастание в LIS? Для строгого — bisect_left, для нестрогого (неубывание) — bisect_right.
Массив tails в LIS — не ответная последовательность. Его длина верна, но содержимое может не быть настоящей LIS; для восстановления самой LIS нужен дополнительный учёт.
LCS-таблица квадратична по памяти; при огромных строках применяют оптимизацию Хиршберга, хранящую лишь две строки.

Итог

LIS — самая длинная возрастающая подпоследовательность; быстрый способ через массив хвостов и бинпоиск даёт O(n log n).
LCS — самая длинная общая подпоследовательность двух строк; двумерное ДП за O(m·n) с восстановлением ответа по таблице назад.
Подпоследовательность — это удаление элементов с сохранением порядка, а не непрерывный кусок.
Следи за строгостью неравенства в LIS и за памятью в LCS.