Изменения
→Решение за время O(N4)
Заполнять <tex> d </tex> будем следующим образом: на очередном шаге сравниваем элементы <tex> a[i] </tex> и <tex> b[j] </tex>:
*Если <tex> a[i] \neq b[j] </tex>, то <tex> d[i][j] = 0 </tex> (так как нет НОВП, оканчивающейся в разных элементах).
*Если <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> prev[1..n] </tex> массива <tex> a: prev[i] </tex> - индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.
prev = int[n] // массив предков
'''for''' i = 1...n
b_i = 1 // ищем лучшую пару (b_i, b_j)
b_j = 1 // d[b_i][b_j] <tex> \rightarrow </tex> max
'''for''' i = 1...n
vector<int> answer
pos = b_i // проходим по массиву a, выписывая элементы НОВП
'''while''' pos != 0
'''return''' answer
