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