12 15 19
|

h2. Indicii de rezolvare

h2. Indicatii 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$) 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":http://infoarena.ro/job_detail/146353?action=view-source .
   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 asemenea solutie se gaseste "aici":http://infoarena.ro/job_detail/146355?action=view-source .