Изменения

Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.

Размещаем граничные случаи: <tex>F(I, I) = 1</tex> и <tex>F(I, J) = 0</tex>, если <tex>I > J</tex>. Теперь в рассматриваемой подстроке отделяем первый символ. Есть две возможности (какая из них реализуется, пока не знаем). Отделенный символ не участвует в образовании максимального подпоследовательности-палиндрома — тогда <tex>F(I, J) = F(I + 1, J)</tex>. Если же участвует, то ищем в подстроке с конца символ, совпадающий с отделенным (пусть его позиция <tex>K</tex>), тогда <tex>F(I, J) = 2 + F(I + 1, K – 1)</tex>. Надо предусмотреть еще случай <tex>I = K</tex>, а затем отсекать рекурсию.