299
правок
Изменения
П2 Mikhail Ermakov
[[Файл:Palindrome11.jpg|200px|thumb|right|Массив длин подпоследовательностей-палиндромов]]
[[Файл:Palindrome12.jpg|200px|thumb|right|Наглядный массив переходов]]
Обозначим данную последовательность через <tex>S</tex>, а ее элементы — через <tex>S[i], 1 <= \le i <= \le n</tex>. Будем рассматривать возможные подпоследовательности данной последовательности с <tex>i - </tex>го по <tex>j-</tex>ый символ, обозначим их как <tex>S(i, j)</tex>. Длины максимальных палиндромов для подпоследовательностей будем записывать в квадратный массив <tex>L</tex>: <tex>L[i][j]</tex> — длина максимальной подпоследовательности-палиндрома, который можно получить из подпоследовательности <tex>S(i, j)</tex>.
Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида <tex>S(i, i)</tex>) ответ очевиден — ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов <tex>S(i, i + 1)</tex> возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.
