Изменения

Размещаем граничные случаи: <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>, а затем отсекать рекурсию.

Получается следующая функция:

Function F(i, j)

if L[i, j] == -1

L[i, j] = R2

return L[i, j]

== Литература ==

== См. также ==

[[Категория:Дискретная математика и алгоритмы]]

[[Категория:Динамическое программирование]]