299
правок
Изменения
Редактирование из-за бага в Опере Ermakov Mikhail
== Определения ==
{{Определение|id = def1. |neat = 1|definition='''Палиндромом''' называется строка, которая одинаково читается как слева направо, так и справа налево.}} {{Определение|id = def2. |neat = 1|definition='''Подпоследовательностью-палиндромом данной строки''' называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''. }}__TOC__
== Решение ==
Обозначим данную последовательность через <tex>S</tex>, а ее элементы — через <tex>S[i], 1 <= i <= 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>.
