Изменения
→Решение за время O(N2)
==Решение за время O(N<sup>2</sup>)==
Модифицируем предыдущее решение, добавив небольшую "хитрость". Теперь <tex> d[i][j] </tex> - это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, причем элемент <tex> b[j] </tex> - последний представитель НОВП, а <tex> a[i] </tex> может не быть таковым. Вычислять <tex> d </tex> будем всё так же: сначала по увеличению <tex> i </tex>, а при равенстве - по увеличению <tex> j </tex>. Тогда для очередного значения <tex> d[i][j] </tex> есть два варианта:
*<tex> a[i] </tex> не входит в НОВП. Тогда <tex> d[i][j] = d[i-1][j] </tex>: значение динамики уже посчитано на префиксе <tex> a[1..i-1] </tex>.
*<tex> a[i] </tex> входит в НОВП. Это значит, что <tex> a[i] = b[j] </tex>, то есть для подсчёта <tex> d[i][j] </tex> нужно пробегать циклом по <tex> b </tex> в поисках элемента, меньшего <tex> b[k] < b[j] </tex> с наибольшей наибольшим значением <tex> d[i-1][k] </tex>. Но мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex>, поэтому будем считать <tex> a[i] </tex> ''фиксированным''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[k] </tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> best </tex>_<tex>ind </tex> в массиве <tex> b </tex>) такой, что этот элемент строго меньше <tex> a[i] </tex> (а также меньше <tex> b[i] </tex>) и значение динамики для него максимально: <tex> b[ind] < a[i] = b[i] </tex> и <tex> best = d[i-1][ind] \rightarrow </tex> max.
vector<int> '''LCIS'''(vector<int> a, vector<int> b)
d = int[n][m] // динамика
prev = int[n] // массив предков
'''for''' i = 1...n
best = 0 // значение динамики для "лучшего" элемента
'''for''' j = 1...m
'''if''' a[i] == b[j] '''and''' d[i-1][j] < best + 1 // используем a[i]-й элемент для увеличения НОВП
d[i][j] = best + 1
p[j] = best_ind ind
'''if''' a[i] > b[j] '''and''' d[i-1][j] > best // при следующем равенстве a[i] == b[j']
best = d[i-1][j] // в best будет храниться "лучший" элемент:
// восстановление (по массиву b)
b_j = 1 // ищем лучший элемент d[n][b_j]<tex> \rightarrow </tex> max
