Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35
Nejdelší rostoucí podposloupnost
(Dynamické Programování)
Posloupnost čísel. Jaká je její nejdelší rostoucí podposloupnost?
Jedu od konce:
mn := max délka podposloupnosti začínající an
mn = max { ai : i>n & ai>an } + 1
Kvadratický čas a lineární paměť (maxima bych si mohl ještě pamatovat).