Изменения
→Решение за время O(N2)
vector<int> '''LCIS'''(vector<int> a, vector<int> b)
d = int[n][m] // динамика 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'] best = d[i-1][j] // нам не придётся бежать циклом в поисках элемента kbest будет храниться "лучший" элемент: best_ind = j // b[kbest_ind] < b[j'] = aи d[i]. Мы считаем элемент a[ibest_ind] фиксированным и сравниваем кандидатов с ним- максимальна
// восстановление (по массиву b)
b_j = 1 // ищем лучший элемент d[n][b_j]<tex> \rightarrow </tex> max
