Изменения

Обозначим как <math>a_{i, j}</math> НОП префиксов данных последовательностей длины , заканчивающихся в элементах с номерами <math>i</math> и <math>j</math> соответственно.Получаем следующее рекуррентное соотношение:

*<math>a_{i, j} = max(a_{i, j - 1}, a_{i - 1, j})</math>, если <math>ss1[i] <> ss2[j]</math> (соответствующие элементы последовательностей не равны).Очевидно, что сложность алгоритма составит <math>O(n^2)</math>.

Предположим, что некоторое значение <math>a_{i, j}</math> посчитано неверно. Однако, в случае равенства различия соответствующих символов, они не могут одновременно участвовать в НОП, а значит ответ действительно равен формуле для случая с различными символами. В случае же равенства, ответ не может быть больше, чем <math>a_{i - 1, j - 1} + 1</math>, так как тогда неверно посчитано значение <math>a_{i - 1, j - 1} + 1</math>.

== Итого =Построение подпоследовательности ===Для каждой пары элементов будем хранить не только длину НОП соответствующих префиксов, но и номера последних элементов, участвующих в этой НОП.Таким образом, посчитав ответ, мы сможем восстановить всю наибольшую общую подпоследовательность.

== Спасибо за внимание=Пример реализации на Java === <font size = 3> public int[] lcs(int[] s1, int[] s2) { int[][] a = new int[s1.length][s2.length]; int[][] last_1 = new int[s1.length][s2.length]; int[][] last_2 = new int[s1.length][s2.length]; //Подсчет значений for (int i = 0; i < s1.length; i++) for (int j = 0; j < s2.length; j++) { if (s1[i] == s2[j]) if ((i == 0) || (j == 0)) { a[i][j] = 1; last_1[i][j] = i; last_2[i][j] = j; } else { a[i][j] = a[i - 1][j - 1] + 1; last_1[i][j] = i; last_2[i][j] = j; } else { if ((i > 0) && (a[i - 1][j] > a[i][j])) { a[i][j] = a[i - 1][j]; last_1[i][j] = last_1[i - 1][j]; last_2[i][j] = last_2[i - 1][j]; } if ((j > 0) && (a[i][j - 1] > a[i][j])) { a[i][j] = a[i][j - 1]; last_1[i][j] = last_1[i][j - 1]; last_2[i][j] = last_2[i][j - 1]; } } } //Восстановление последовательности int l = a[s1.length - 1][s2.length - 1]; int[] ans = new int[l]; int ti = s1.length - 1; int tj = s2.length - 1; while (l > 0){ ans[l - 1] = s1[last_1[ti][tj]]; int nti = last_1[ti][tj] - 1; int ntj = last_2[ti][tj] - 1; ti = nti; tj = ntj; l--; } return ans; }</font>