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

Fie un vector $a$ cu $N$ elemente. Numim subsir al lui $a$ de lungime $K$ un vector $a'$ =  ({$a{~i{~1~}~}$}, $a{~i{~2~}~}$, ..., {$a{~i{~K~}~}$}) astfel incat sa avem $i{~1~}$ < {$i{~2~}$} < ... < {$i{~K~}$}.

Fie un vector $a$ cu $N$ elemente. Numim subir al lui $a$ de lungime $K$ un vector $a'$ =  ({$a{~i{~1~}~}$}, $a{~i{~2~}~}$, ..., {$a{~i{~K~}~}$}) astfel incat sa avem $i{~1~}$ < {$i{~2~}$} < ... < {$i{~K~}$}.

h2. Cerinta

h2. Restrictii

* $1 ≤ N ≤ 100 000$
* {$1 ≤ a{~i~} ≤ 2 000 000 000$}, pentru orice $i$ de la $1$ la $N$

* $1 ≤ $N$ ≤ 100 000$
* $1$ ≤ $a{~i~}$ ≤ $2 000 000 000$ , pentru orice $i$ de la $1$ la $N$

* Se acorda 50% din punctaj daca este afisata corect doar lungimea celui mai lung subsir crescator
h2. Exemplu

Complexitatea optima este {$O(N*log{~2~}N)$}. La fiecare pas $i$ trebuie determinata lungimea cea mai mare $best{~j~}$ unde {$1 &le; j < i$} astfel incat {$a{~j~}$} &le; {$a{~i~}$}. Pentru a afla aceasta informatie in timp optim {$O(log{~2~}N)$} se poate folosi un arbore de intervale sau un arbore indexat binar. O astfel de abordare obtine 100 de puncte si se gaseste 'aici':job_detail/146356?action=view-source. O alta idee de rezolvare ce obtine punctajul maxim, dar mai simplu de implementat si mai rapida, se gaseste 'aici':job_detail/146355?action=view-source. Ideea de rezolvare din spatele acestei solutii se gaseste in cartea lui Catalin Francu, "Psihologia concursurilor de informatica", editura L&S.
== include(page="template/taskfooter" task_id="scmax") ==

 
== SmfTopic(topic_id="2985.0") ==