Изменения

Задача о '''наибольшей подпоследовательности-палиндрома''' — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности.

== Определения ==

{{Определение|definition='''Палиндромом''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}

{{Определение|definition='''Подпоследовательностью-палиндромом данной строки''' называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. }}

'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.

== Решение ==

Перед вызовом процедуры заполняем <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>.

При первой вызове функции, к качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной 7 вызов функции булдет иметь следующий вид: <tex>pal(0,6)</tex>. Искомая же длина будет записана в ячейке <tex>L[0][N-1]</tex>, где <tex>N</tex> — длина исходной строки.

'''pal'''(i, j) //i и j - границы строки S

'''if''' L[i][j] = -1 //L - массив длин

L[i][j] = R2

'''return''' L[i][j]

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