Na vstupe máte postupnosť n celých čísel. Nájdite jej najdlhšiu neklesajúcu podpostupnosť. Inak povedané, vyškrtajte z postupnosti čo najmenej čísel, aby to čo ostalo bola neklesajúca postupnosť čísiel. Zistite dĺžku toho, čo ostalo.
Na prvom riadku je číslo $n$ - počet prvkov postupnosti. Na druhom riadku sa nachádza $n$ medzerou oddelených kladných čísiel.
Vypíšte jedno číslo – dĺžku najdlhšej neklesajúcej podpostupnosti.
4
4 3 2 1
1
6
1 4 1 3 1 4
4
Riešením je postupnosť 1 1 1 4 alebo 1 1 3 4.
8
7 2 7 4 6 1 8 1
4
Riešením je postupnosť 2 4 6 8.