Изменения

'''Наибольшая возрастающая подпоследовательность(НВП)''' (''англ''. Longest increasing subsequence - LIS) строки <tex> x </tex> длины <tex> n </tex> - это последовательность <tex> x[i_1] < x[i_2] < \dots < x[i_k] </tex> символов строки <tex> x </tex> таких, что <tex> i_1 < i_2 < \dots < i_k, 1 \le i_j \le n </tex> и <tex> k </tex> - наибольшее из возможных.

Строим таблицу <tex> Aa[1 \dots n]. Каждый её элемент <tex> Aa[i] </tex> - длина наибольшей возрастающей подпоследовательности, оканчивающейся точно в позиции <tex> i </tex>. Если мы построим эту таблицу, то ответ к задаче - наибольшее число из этой таблицы.Само построение тоже элементарно: ,<tex> Aa[i] = \max{i-1}_{j = 1} {(Aa[j] + 1)} </tex>, для которых <tex> x[j] < x[i] </tex>. База динамики <tex> Aa[1] = 1 </tex>.Если мы хотим восстановить саму подпоследовательность, то заведем массив предыдущих величин pred такой, что pred[i] - предпоследний элемент в НВП, оканчивающейся в элементе с номером <tex> i </tex>. Его значение будет изменяться вместе с изменением соответствующего i-ого элемента матрицы <tex>a</tex>.<code> lis = 0 // длина НВП a = {0..0} // заполняем нулями pred = {-1..-1} // -1 - признак отсутствия предпоследнего элемента, что указывает на то, что данный элемент является первым в подпоследовательности a[1] = 1; For i = 2 to n For j = 1 to i - 1 If (x[i] > x[j]) and (a[j] + 1 > a[i]) // нашли более оптимальную подпоследовательность a[i] = a[j]+1; pred[i] = j; lis = <tex>\max{n}_{i = 1} {a[i]}</tex></code>Для вывода самой подпоследовательности достаточной пройти по массиву pred, начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента.