Урок: наибольшая палиндромная подпоследовательность — зеркало без склейки подряд

Вчера собирали возрастающую цепочку (НВП). Сегодня сосед по семейству подпоследовательностей: наибольшая палиндромная подпоследовательность (НПП, по-английски LPS). Дана строка — нужно найти самую длинную цепочку букв, которая читается одинаково слева направо и справа налево, а порядок индексов сохраняется. Буквы не обязаны стоять рядом: в «BBBAB» ответ BBBB длины 4 (пропускаем A). Это снова не подстрока: подстрока непрерывна, подпоследовательность — нет. Базовый способ — двумерная динамика O(n2). Пусть dp[i][j] — длина НПП на отрезке от i до j включительно. Тогда: — одна буква: dp[i][i] = 1; пустой отрезок даёт 0; — если s[i] совпадает с s[j]: берём внутренний ответ dp[i+1][j−1] и плюс две эти буквы (для длины отрезка ≥ 2); — иначе: max(dp[i+1][j], dp[i][j−1]) — либо отбрасываем левый край, либо правый. Ответ — dp[0][n−1]. Чтобы восстановить саму цепочку, откатываемся от углов таблицы: совпали края — берём букву с обеих сторон и сужаемся; иначе идём в соседнюю ячейку с большим значением. На первой картинке таблица для «BBBAB». Угол dp[0][4] = 4. Откат: (0,4) берём B...B → (1,3) буквы разные, уходим к (1,2) → снова B...B. Сходимся в BBBB. Код — на второй картинке: и длина, и восстановление. Запустили на Python 3.13.5: «BBBAB» → (4, 'BBBB'); «CHARACTER» → (5, 'CARAC'). Что важно помнить. — Мост к вчерашнему НОП: длина LPS(s) равна длине LCS(s, reverse(s)). Можно считать через общую подпоследовательность со своим переворотом; таблица выше — прямой «палиндромный» вариант той же идеи. — Память O(n2) в лоб; если нужна только длина, достаточно двух строк O(n). Восстановление обычно оставляют на полной таблице или отдельном откате. — Где встречается: олимпиадная подготовка, строковые алгоритмы, задача «минимум вставок, чтобы строка стала палиндромом» — ответ как раз n минус длина НПП. Идея в одной фразе: совпали края отрезка — оба входят в ответ и задача сужается внутрь; не совпали — выбираем лучший из двух укороченных отрезков, а таблица dp хранит эти длины для каждой пары границ. #урок