magnify

Ilgiausias didėjantis posekis (2)

Pradinių duomenų failas:
posekis.in  
Rezultatų failas:
posekis.out  
Laiko apribojimas:
2 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Čia – indeksas. O čia – indekso indeksas.
Vienas dėstytojas

Sekos \(a_{1}\), \(a_{2}\), …, \(a_{n}\) posekiu vadinama seka \(a_{j_{1}}\), \(a_{j_{2}}\), …, \(a_{j_{k}}\), kur 1 <= \(j_{1}\) < \(j_{2}\) < … < \(j_{k}\) <= n.

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 pradinių duomenų failo eilutėje įrašytas skaičius n (1 <= n <= 1000000). Antroje eilutėje įrašyti sekos nariai \(a_{1}\), \(a_{2}\), …, \(a_{n}\), atskirti tarpais (1 <= \(a_{i}\) <= 1 000 000 000).

Rezultatai

Į rezultatų failą turi būti įrašytas vienas skaičius – ilgiausio duotosios sekos didėjančio posekio ilgis.

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.
© Bronė Narkevičienė