Изменения

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