Laiko ribojimas: 2s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Ilgiausias didėjantis posekis

Sekos a_1,a_2,...,a_n posekiu vadinama seka a_{j1},a_{j2},...,a_{jk}, kur 1\\lej_1<j_2<...<j_k\\len.

Seka a_1,a_2,...,a_n vadinama didėjančia, jei a_1<a_2<...<a_n.

Parašykite programą, kuri rastų ilgiausio duotosios sekos didėjančio posekio ilgį.

Pradiniai duomenys

Pirmoje įvesties eilutėje irašytas skaicius n (1\\len\\le1000). Antroje eilutėje įrašyti sekos nariai a_1,a_2,...,a_n, atskirti tarpais (1\\lea_i\\le1000000000).

Rezultatai

Išveskite vieną skaičių - ilgiausio duotosios sekos didėjančio posekio ilgį.

Pavyzdys

Pradiniai duomenys Rezultatai Paaiškinimas
4
2 6 1 3
2
Ilgiausi didėjantys posekiai yra keli: (2, 6), (2, 3), (1, 3). Ilgesnio didėjančio posekio nėra.
11
6 3 12 10 4 11 6 1 8 12 7
5
Ilgiausias didėjantis posekis šioje sekoje: 3 4 6 8 12.