Изменения

Рассмотрим решение на примере последовательности '''''ABACCBA'''''. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями <tex>S(i, i)</tex> из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме <tex>S(4, 5)</tex>, элементы различны, поэтому в соответствующие ячейки запишем <tex>1</tex>, а в <tex>L[43][54]</tex> — <tex>2</tex>.

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали. Для подпоследовательностей длины <tex>3</tex> получаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, поэтому <tex>L[10][32] = L[21][21] + 2</tex>. В остальных подпоследовательностях первый и последний элементы различны.

'''''BAC''''': <tex>L[21][43] = max(L[21][32], L[32][43]) = 1</tex>

'''''ACC''''': <tex>L[32][54] = max(L[32][43], L[43][54]) = 2</tex>

'''''CCB''''': <tex>L[43][65] = max(L[43][54], L[54][65]) = 2</tex>

'''''CBA''''': <tex>L[54][76] = max(L[54][65], L[65][76]) = 1</tex>

Продолжая далее аналогичные рассуждения, заполним все ячейки под диагональю и в ячейке <tex>L[10][76]</tex> получим ответ <tex>(6)</tex>.