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