Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | bitonic.in, bitonic.out | Sursă | ONIS 2014, Runda 3 |
| Autor | Stefan Ciobaca | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bitonic
Un şir de numere a~1~, a~2~, ..., a~k~ este bitonic dacă există o poziţie 1 &le i &le n astfel încât a1 < a2 < ... < a[i] > a[i+1] > ... > a[k] sau a1 > a2 > ... > a[i] < a[i+1] < ... < a[k].
Dându-se un şir, să se găsească lungimea celui mai lung subşir bitonic.
Date de intrare
Fişierul de intrare bitonic.in conţine pe prima linie numărul T de teste, iar următoarele linii conţin testele. Fiecare test are două linii: pe prima linie se găseşte numărul n de elemente ale şirului şi următoarea linie conţine şirul.
Date de ieşire
În fişierul de ieşire bitonic.out se va afişa pentru fiecare test câte o linie conţinând lungimea maximă a unui subşir bitonic al şirului de la intrare.
Restricţii
- $ 1 ≤ T ≤ 20 $
- $ 1 ≤ n ≤ 1000 $
- elementele şirului iniţial sunt numere naturale între 0 şi 100000
Exemplu
| bitonic.in | bitonic.out |
|---|---|
| 2 7 1 10 5 11 1 3 12 2 10 1 10 2 3 7 6 5 4 8 9 | 5 7 |
Explicaţie
Pentru primul exemplu un subşir bitonic de lungime maximă este 1 5 11 3 2 iar pentru al doilea exemplu 1 2 3 7 6 5 4.
