Изменения
→Решение за время O(N3)
*Если <tex> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </tex> - максимальна.
<texdpi="120"> d[i][j] = \max(\limits_{k = 1..i-1} d[k][j]) + 1, </tex> для всех при условии, что <tex> k = 1..i-1, a[k] < a[i]. </tex>
Длина НОВП будет в элементе с максимальным значением <tex> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </tex>, как и в предыдущем решении.
'''if''' a[i] == b[j]
d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
'''else'''
d[i][j] = d[i][j-1]
