Nejdelší rostoucí podposloupnost
(
Dynamické Programování)
Posloupnost čísel. Jaká je její nejdelší rostoucí podposloupnost?
Jedu od konce:
m
n := max délka podposloupnosti začínající a
n
m
n = max { a
i : i>n & a
i>a
n } + 1
Kvadratický čas a lineární paměť (maxima bych si mohl ještě pamatovat).
