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 a1, a2, ..., ak este bitonic dacă există o poziţie 1 ≤ i ≤ n astfel încât a1 < a2 < ... < ai > ai+1 > ... > ak sau a1 > a2 > ... > ai < ai+1 < ... < ak.
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 |
|---|---|
| 3 7 1 10 5 11 1 3 12 2 10 1 10 2 3 7 6 5 4 8 9 3 1 2 5 3 4 | 5 7 4 |
Explicaţie
Pentru primul test un subşir bitonic de lungime maximă este 1 5 11 3 2, pentru al doilea test 1 2 3 7 6 5 4 şi pentru ultimul test 1 2 3 4.
