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