Изменения

Перейти к: навигация, поиск
Решение за время O(N3)
'''for''' j = 1...m
'''if''' a[i] == b[j]
d[i][j] := 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
'''for''' k = 1...i-1
'''if''' a[k] < a[i] '''and''' d[i][j] < d[k][j] + 1
prev[i] := k
'''else'''
d[i][j] = d[i][j-1] // "протаскиваем" предыдущее удачное сравнение
// восстановление
b_i := 1 // ищем лучший элемент d[b_i][m] <tex> \rightarrow </tex> max
Анонимный участник

Навигация