Изменения

'''Наибольшая возрастающая подпоследовательность (НВП)''' (''англ''. 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> 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>.

Для вывода самой подпоследовательности достаточной пройти по массиву <tex>prev</tex>, начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента.

Для более быстрого решения данной задачи построим следующую динамику: пусть <tex>d[i](i = 0...n)</tex> - число, на которое оканчивается возрастающая последовательность длины <tex>i</tex>, а если таких чисел несколько - то наименьшее из них. Изначально мы предполагаем, что <tex>d[0] = -</tex><tex>\infty</tex>, а все остальные элементы <tex>d[i] =</tex> <tex>\infty</tex>.

Заметим два важных свойства этой динамики: <tex>d[i - 1] <= d[i]</tex>, для всех <tex>i = 1...n</tex>. А так же что каждый элемент <tex>a[i]</tex> обновляет максимум один элемент <tex>d[j]</tex>. Это означает, что при обработке очередного <tex>a[i]</tex>, мы можем за <tex> O(n\cdot\log n) </tex> c помощью двоичного поиска в массиве <tex>d[]</tex> найти первое число, которое строго больше текущего <tex>a[i]</tex> и обновить его.