Na cvičení jsme si ukazovali vybrané zápočtové programy z minulých let
a také řešili následující úlohu:
Na vstupu je dána posloupnost kladných celých čísel ukončená nulou. Najděte délku nejdelší rostoucí
podposloupnosti dané posloupnosti. Např. v posloupnosti 4 2 7 6 4 5 3 9 8 5 9 má nejdelší rostoucí
podposloupnost délku 5 a je vyznačena červeně.
Úlohu lze řešit přímočaře, ale velmi neefektivně s faktoriálovou složitostí a nebo efektivněji s kvadratickou
složitostí. Ještě lepší řešení můžete najít v knize:
Od problému k algoritmu. Ivan Libicher, Pavel Topfer, Praha 1992.