Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : ÚlohaNejdelšíRostoucíPodposloupnost

Matfiz: ÚlohaNejdelšíRostoucíPodposloupnost

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).