Изменения

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

Для строки ''x'' будем по-прежнему хранить массивы <tex>a</tex> (a уже длины 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[10] < a[21] < a[32] < \dots < a[n] </tex>. Пусть мы находимся на i-ом шаге, тогда нам надо найти такой номер k <tex> a[k] \leqslant x[i] < a[k+1] </tex> (если положить при начальной реализации<tex> a[10] = -\inf a[21] = a[32] = \dots = a[n] = \inf </tex>, то такое k всегда найдется).Причем если в условии не строгое возрастание, то массив a ''не убывает'', и надо искать наибольшее 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>.