h2. Restrictii
* $1 ≤ $N$ ≤ 1000.$

* $1$ ≤ $a{~i~}$ ≤ $50000$ , pentru orice $i$ = 1, $N$ .

* $1$ ≤ $a{~i~}$ ≤ $2.000.000.000$ , pentru orice $i$ = 1, $N$ .

* Daca exista mai multe solutii se poate afisa oricare.
* Se acorda 50% din punctaj daca este afisata corect doar lungimea celui mai lung subsir crescator.

  12 15 19
|

h3. Explicatie

h3. Indicii de rezolvare
 
Problema se rezolva folosind programarea dinamica. Se noteaza $best{~i~}$ - lungimea maxima a unui subsir crescator care se termina pe pozitia $i$ . Obtinem astfel urmatoarea relatie: $best{~i~}$ = max ( $1$ , max( $a{~j~})$ + $1$ | $1$ $le; $j$ < $i$ si $a{~j~}$ < $a{~i~}$ .
 La pasul i trebuie sa gasesti lungimea cea mai mare L[j] unde 1 <= j < i astfel incat a[j] <= a[i]. Ai putea sau sa folosesti un arbore de intervale pentru asta, sau sa folosesti un sir in care in elementul x pastrezi cel mai mic element in care se termina un subsir de lungime x. Gasesti pe net sau in cartea lui Catalin Francu o explicatie mai detaliata.

*Feedback(Cosmin):* Nu punem si solutia in O(n log n)?
*Raspuns(Florian):* Din pacate nu stiu solutia in NlogN. Dar daca imi spui ideea cred ca ma prind. Si vedem ce putem face.
*Cosmin:* La pasul i trebuie sa gasesti lungimea cea mai mare L[j] unde 1 <= j < i astfel incat a[j] <= a[i]. Ai putea sau sa folosesti un arbore de intervale pentru asta, sau sa folosesti un sir in care in elementul x pastrezi cel mai mic element in care se termina un subsir de lungime x. Gasesti pe net sau in cartea lui Catalin Francu o explicatie mai detaliata.
*Florian:* Parearea mea e ca se complica putin lucrurile si problema nu mai e dinamica pura. Insa, daca e neaparata nevoie, voi mari $N$-ul ca sa nu intre in timp O(n^2).

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