## Hello 2
### Hello 3

!sandbox?IA_bug_in_FF2.jpg!

!sandbox?IA_bug_in_FF2.jpg!
 
 
h2. Subsir 2
 
h3. (problema grea clasa a 9a, problema medie clasa a 10a, problema usoara clasele 11-12)
 
Problema poate fi considerata asemanatoare cu cea a celui mai lung subsir crescator, avand o rezolvare similara de complexitatea $O(N^2^)$ folosind metoda programarii dinamice.
 
Se vor construi doi vectori:
 
* $A{~i~}$ = lungimea celui mai scurt subsir crescator maximal care incepe cu pozitia $i$
* $T{~i~}$ = urmatorul element dupa pozitia $i$ in cel mai scurt subsir crescator maximal care incepe cu $i$ (pentru reconstiutire)
 
Pentru fiecare {$i$}, se va cauta un $j > i$ astfel incat {$V{~i~} ≤ V{~j~}$} (unde $V$ este vectorul de numere) si se alege acela cu $A{~j~}$ minim, $A{~i~}$ devenind {$A{~j~}+1$}, iar $T{~i~}$ devine {$j$}. Daca nu exista nici un {$j$}, $A{~i~}$ se initializeaza cu $1$ si $T{~i~}$ cu {$i$}.
 
Ca sirul construit sa fie maximal trebuie ca atunci cand verificam {$j$}-urile pentru un $i$ fixat, {$j$}-ul respectiv sa fie "dominant", in sensul ca sa nu existe un $i < k < j$ astfel incat {$V{~i~} &le; V{~k~} &le; V{~j~}$}, deoarece sirul construit cu primul element in $i$ si al doilea in $j$ ar putea fi extins inserand $k$ intre $i$ si {$j$}. Verificarea pentru acest $k$ se poate face in {$O(N)$}, obtinand o solutie $O(N^3^)$ care ar fi adus {$50-60p$}. Pentru a face verificarea in {$O(1)$}, facem observatia ca ne intereseaza doar acel $V{~k~}$ minim care este &ge; {$V{~i~}$}. Pe masura ce se avanseaza cu variabila {$j$}, se pastreaza o variabila {$min$}, reprezentand minimul dintre valorile $V{~j~}$ parcurse pana acum, care sunt &ge; {$V{~i~}$}.
 
Astfel, cand se ajunge la un {$j$}, se verifica inainte daca {$V{~j~} < min$} (conditie necesara pentru a construi un sir maximal). Un ultim detaliu in solutie este obtinerea solutiei minime din punct de vedere lexicografic. Cand se selecteaza {$j$}-ul pentru fiecare {$i$}, pe langa faptul ca se alege acela cu $A{~j~}$ minim, in caz de egalitate se va alege acela cu valoarea $V{~j~}$ minima. Selectarea este corecta deoarece nu vor exista {$j1$}, $j2$ cu $A{~j1~}$ si $A{~j2~}$ minim , iar {$V{~j1~} = V{~j2~}$}.
Problema se poate rezolva mai bine intr-o complexitate $O(N*lg^2^ N)$ folosind structuri de date avansate, astfel transformandu-se intr-o problema de clasele 11-12 grea, sau chiar o problema de finala. Lasam aceasta rezolvare ca exercitiu pentru cititor.