Изменения
→Решение за время O(N3)
<tex> d[i][j] = max(d[k][j]) + 1, </tex> для всех <tex> k = 1..i-1, a[k] < a[i]. </tex>
Длина НОВП будет в элементе с максимальным значением <tex> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </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
d[i][j] = d[i][j-1]
// восстановление
pos = 1 // ищем лучший элемент c максимальным d[pos][m] <tex> \rightarrow </tex> max
'''for''' i = 1...n
'''if''' d[pos][m] < d[i][m]
