Изменения

Для строки ''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+1] </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.

for For i = 1 to n j = upper_bound(1, n, x[i]) // бинарный поиск наибольшего индекса среди всех j ≤ L< i, удовлетворяющего удовлетворяющих x[a[j]] < x[i] Ppred[i] = Ma[j] if If j == L i or Xx[i] < X[M[j+1]] // нашли более оптимальную подпоследовательность