Изменения
→Решение за время O(N2)
prev = int[n] // массив предков
'''for''' i = 1...n
best_ind := 0 //позиция "лучшего" элемента в массиве b best := 0 //значение динамики для "лучшего" элемента
'''for''' j = 1...m
d[i][j] := d[i-1][j] // НОВП на префиксе a[1..i-1] и b[1..j], то есть без элемента a[i]
'''if''' a[i] == b[j] '''and''' d[i-1][j] < best + 1 // можем использовать a[i]-тый элемент для увеличения НОВП
d[i][j] := best + 1 p[j] := best_ind
'''if''' a[i] > b[j] '''and''' d[i-1][j] > best // в момент следующего равенства a[i] = b[j'] нам не придётся бежать циклом в поисках элемента k:
best := d[i-1][j] // b[k] < b[j'] = a[i]. Мы считаем элемент a[i] фиксированным и сравниваем кандидатов с ним best_ind := j
// восстановление (по массиву b)
b_j := 1 // ищем лучший элемент d[n][b_j]<tex> \rightarrow </tex> max
'''for''' k = 1...m
'''if''' d[n][b_j] < d[n][j]
b_j := j
vector<int> answer
pos := b_j //проходим по массиву b, выписывая элементы НОВП
'''while''' pos != 0
answer.push(b[pos])
