Изменения

Перейти к: навигация, поиск
Решение за время O(N2)
'''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 prev[j] = ind '''if''' a[i] > b[j] '''and''' d[i-1][j] > best // при следующем равенстве a[i] == b[j'] best = d[i-1][j] // в best будет храниться "лучший" элемент: ind = j // b[ind] < b[j'] и d[i][ind] <tex> \rightarrow </tex> max
// восстановление (по массиву b)
pos = 1 // ищем лучший элемент d[n][pos] <tex> \rightarrow </tex> max
Анонимный участник

Навигация