Diferențe pentru problema/s2c între reviziile #4 si #7

== include(page="template/taskheader" task_id="s2c") ==
Fie un șir format din $N$ numere naturale nenule: $a[&#49;], a[&#50;], ..., a[N].$ Se numește *subșir 2-crescător de lungime [$k$]* al șirului dat orice subșir $a[x[~1~]], a[x[~2~]], ..., a[x[~k~]],$ unde $1 ≤ x[~1~] < x[~2~] < ... < x[~k~] ≤ N,$ în care este îndeplinită următoarea proprietate:


a[x i ] < a[x i+2 ], pentru orice i, 1 ≤ i ≤ k - 2, adică a[x 1 ] < a[x 3 ] <
a[x 5 ] < ... și a[x 2 ] < a[x 4 ] < a[x 6 ] < ...

 
* $a[x[~i~]] < a[x[~i+2~]],$ pentru orice $i, 1 ≤ i ≤ k - 2,$ adică $a[x[~1~]] < a[x[~3~]] < a[x[~5~]] < ...$ și $a[x[~2~]] < a[x[~4~]] < a[x[~6~]] < ...$
 
h2. Cerință
 
Date fiind $T$ șiruri conform enunțului, se cere să se determine *lungimea maximă a câte unui subșir 2-crescător pentru fiecare dintre cele $T$ șiruri date.*

h2. Date de intrare

Fișierul de intrare $s2c.in$ ...

În fișierul de intrare $s2c.in$ se află pe prima linie numărul [$T$], reprezentând numărul de șiruri, iar pe fiecare dintre următoarele $2*T$ linii se află descrierile șirurilor. Pe linia $2*i$ se va afla un singur număr natural reprezentând numărul de elemente $N[~i~]$ al celui de-al [$i$]-lea șir de numere dat. Pe linia $2*i+1$ se vor afla $N[~i~]$ numere naturale, reprezentând numerele din șir, separate prin câte un spațiu.

h2. Date de ieșire

În fișierul de ieșire $s2c.out$ ...

În fișierul de ieșire $s2c.out$ se vor scrie $T$ linii, fiecare conținând un singur număr natural. Pe linia $i$ se va scrie un număr natural reprezentând *lungimea maximă a unui subșir 2-crescător* al celui de-al [$i$]-lea șir din cadrul celor $T$ șiruri date.

h2. Restricții

h2. Restricții și precizări

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 10$
* $1 ≤ N[~i~] ≤ 2.000$, pentru fiecare [$i$], $1 ≤ i ≤ T$.
* Pentru 30% din punctaj $1 ≤ N[~i~] ≤ 400$, pentru fiecare [$i$], $1 ≤ i ≤ T$.
* Pentru 60% din punctaj $1 ≤ N[~i~] ≤ 1.000$, pentru fiecare [$i$], $1 ≤ i ≤ T$.
* Elementele din fiecare șir sunt numere naturale nenule din mulțimea {1, 2, 3, ..., 30.000}.

h2. Exemplu
table(example).

|_. s2c.in |_. s2c.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
 
...

|_. s2c.in |_. s2c.out |_. Explicații |
| 2
8
1 1 3 2 5 3 4 5
5
9 6 4 2 7
| 6
3
| Avem T = 2 teste.
Primul șir are lungimea egală cu 8. Subșirurile 2-crescătoare de lungime maximă, egală cu 6, sunt:
 
1 1 3 2 5 3
1 1 3 2 5 4
1 1 3 2 5 5
1 1 3 2 4 5
1 1 2 3 4 5
 
Al doilea șir are lungimea 5. Subșirurile 2-crescătoare de lungime maximă, egală cu 3, sunt:
 
6 4 7
6 2 7
4 2 7
|

== include(page="template/taskfooter" task_id="s2c") ==