Írj programot, ami megadja egy adott sorozat leghosszabb monoton növekvő részsorozatának hosszát! Részsorozat alatt a sorozat tagjainak tetszőleges részhalmazát értjük (tehát NEM feltétlenül egymás utáni elemekből áll), az eredeti sorozatban levő sorrendjüket megtartva. Monoton növekvő sorozatban minden tag legalább annyi, mint az előtte levők.
A sorozatnak legfeljebb 100000 (10^5) tagja van, amelyek pozitív számok 1 és 100000000 (10^8) között (a határokat is beleértve).
A bementi fájl első sorában a tesztesetek t száma található, utána 2*t sorban a tesztesetek leírása. Minden teszteset első sorában a sorozat n hossza, a második sorában pedig n db szám: a sorozat.
Tesztesetenként 1 szám: a leghosszabb monoton növekvő részsorozat hossza.
Bemenet:
1
9
1 5 2 3 4 2 5 1 6
Kimenet:
6
Magyarázat:
A leghosszabb sorozat: 1 2 3 4 5 6.
(A feladatot kidolgozta: Englert Péter)