Изменения

a = {(n, 0..0} ) // заполняем нулями pred = {-1..(n, -1} ) // -1 - признак отсутствия предпоследнего элемента, что указывает на то, что данный элемент является первым в подпоследовательности

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

a = (n + 1, inf) pred = (n, -1) a[10] = -inf ano[2..n0] = inf-1

j = upper_boundbinary_search(10, n, x[i]) // бинарный поиск наибольшего индекса среди всех j < i, удовлетворяющих удовлетворяющего x[a[j]] < x[i] predи x[i] = < x[a[j+ 1]] If d[j + 1] = a[i or x] p[i] < X[M= no[j+1]] // нашли более оптимальную подпоследовательность M no[j+1] = i L = max{L, j+1};