Изменения
Нет описания правки
Известно несколько алгоритмов решения этой задачи.
==== Пример алгоритма, работающего за время <tex> O(n^2) </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>.
Если мы хотим восстановить саму подпоследовательность, то заведем массив предыдущих величин pred такой, что pred[i] - предпоследний элемент в НВП, оканчивающейся в элементе с номером <tex> i </tex>. Его значение будет изменяться вместе с изменением соответствующего i-ого элемента матрицы <tex>a</tex>.
<code>
lis = max(lis, a[i])
</code>
Для вывода самой подпоследовательности достаточной пройти по массиву <tex>pred</tex>, начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента.
==== Пример алгоритма, работающего за время <tex> O(n\cdot\log n) </tex> ====
Для строки ''x'' будем по-прежнему хранить массивы <tex>a</tex> (<tex>a </tex> уже длины n + 1) и <tex>pred</tex>, добавим к ним так же массив no из n + 1 элементов так, что в no[i] хранится номер последнего элемента в возрастающей подпоследовательности длины i. Теперь <tex> a[i] </tex> содержит наименьший по величине элемент, на который может оканчиваться возрастающая подпоследовательность длины <tex>i</tex>, среди всех <tex>x[j]</tex>, где <tex>1 \leqslant j \leqslant i-1 </tex>, если мы на шаге <tex>i</tex>. В свою очередь, pred[i] хранит индекс предшевствующего символа для наибольшей возрастающей подпоследовательности, оканчивающейся в i-й позиции. Заметим, что <tex> a[0] < a[1] < a[2] < \dots < a[n] </tex>. Пусть мы находимся на i-ом шаге, тогда нам надо найти такой номер k <tex> a[k] \leqslant x[i] < a[k+1] </tex> (если положить при начальной реализации<tex> a[0] = -\inf , a[1] = a[2] = \dots = a[n] = \inf </tex>, то такое k всегда найдется).Причем если в условии не строгое возрастание, то массив <tex>a </tex> ''не убывает'', и надо искать наибольшее k из возможных. После этого полагаем <tex> a[k + 1] = x[i] </tex>, а остальные элементы массива не меняем. В силу упорядоченности массива a, мы можем искать k бинарным поиском (при не строгом возрастании необходимо пользоваться функцией upper_bound(1, n, a[i])). Параллельно нахождению НВП будем записывать массив предков pred и номеров no. Подсчитаем время: мы n раз выпоняем бинарный поиск, что требует <tex> O(\log n) </tex> времени. Итого: <tex> O(n\cdot\log n) </tex>.
<code>
