Изменения
→Решение за время O(N4)
*Если <tex> a[i] = b[j] </tex>, то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах <tex> a </tex> и <tex> b </tex>. Заметим, что предыдущие значения <tex> d </tex> уже известны, тогда очередное значение <tex> d[i][j] = max(d[k][l]) + 1, </tex> для всех <tex> k = 1..i-1 </tex> и <tex> l = 1..j-1, </tex> при условии, что <tex> a[k] = b[l]. </tex>
Длина НОВП будет в элементе с максимальным значением <tex> d[i][j] </tex>. Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> - индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.
vector<int> '''LCIS'''(vector<int> a, vector<int> b)
