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.

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$) cu $1$ &le; $j$ < $i$ si $a{~j~}$ < $a{~i~}$ . Pentru a reconstrui solutia mai retinem un vector cu semnificatia $pre{~i~}$ - pozitia valorii care preceda elementul $i$ in subsirul crescator care se termina pe pozitia $i$. Aceasta solutie are complexitatea $O(N^2)$ si obtine 70 de puncte. O astfel de solutie gasiti aici.
   Complexitatea solutiei de $100$ de puncte este O(N*logN). Aceasta consta in: la pasul i trebuie sa gasiti lungimea cea mai mare $L{~j~}$ unde 1 &le; $j$ < $i$ astfel incat a{~j~} &le; a{~i~}. Puteti sa folositi un arbore de intervale pentru asta sau un sir in care in elementul $x$ pastrati cel mai mic element in care se termina un subsir de lungime $x$ . Gasiti pe net sau in cartea lui Catalin Francu o explicatie mai detaliata. O asemnea solutie se gaseste aici.

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