299
правок
Изменения
→Пример
'''''CBA''''': <tex>L[4][6] = max(L[4][5], L[5][6]) = 1</tex>
Продолжая далее аналогичные рассуждения, заполним все ячейки под над диагональю и в ячейке <tex>L[0][6]</tex> получим ответ <tex>(6)</tex>.
Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.
Последовательность заполнения массива и массив переходов см. на изображениях ниже.
[[Файл:Palindrome11.png|200px|Заполнение массива длин (1)]]
[[Файл:Palindrome14.png|200px|Заполнение массива длин (4)]]
[[Файл:Palindrome15.png|200px|Массив переходов]]
== Псевдокод ==
Перед вызовом процедуры заполняем <tex>L[][]</tex> начальными значениями: <tex>L[i][j] = 1</tex> если <tex>i=j</tex>, <tex>L[i][j] = 0</tex>, если <tex>i>j</tex>, в остальных случаях <tex>L[i][j]=-1</tex>.
