Изменения
Нет описания правки
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 = max(lis, a[i])
</code>
Для вывода самой подпоследовательности достаточной пройти по массиву pred, начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента.
==== Пример алгоритма, работающего за время <tex> O(n*\log n) </tex> ====
Для строки ''x'' будем по-прежнему хранить массивы <tex>a</tex> и <tex>pred</tex> длины n. Только теперь <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[1] < a[2] < a[3] < \dots < a[n] </tex>. Пусть мы находимся на i-ом шаге, тогда нам надо найти такой номер k <tex> a[k-1] < x[i] < a[k] </tex> (если положить при начальной реализации<tex> a[1] = -\inf a[2] = a[3] = \dots = a[n] = \inf </tex>, то такое k всегда найдется), причем надо наибольшее k из возможных. После этого полагаем <tex> a[k] = x[i] </tex>. В силу упорядоченности массива a, мы можем выполнить поиск k бинарным поиском, а име нно, функцией upper_bound(begin, end, val), максимальный возвращающий номер элемента, который меньше (или не больше, зависит от постановки задачи), чем val.
<code>
lis = index = 0
a[1] = -inf
a[2..n] = inf
for i = 1 to n
j = upper_bound(бинарный поиск наибольшего индекса j ≤ L, удовлетворяющего x[a[j]] < x[i]
P[i] = M[j]
if j == L or X[i] < X[M[j+1]] // нашли более оптимальную подпоследовательность
M[j+1] = i
L = max{L, j+1}
</code>
