Fişierul intrare/ieşire:	scmax.in, scmax.out	Sursă	ad-hoc
Autor	Arhiva Educationala	Adăugată de	Florian Marcu •Florian
Timp execuţie pe test	0.15 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Subsir crescator maximal

Fie un vector a cu N elemente. Numim subir al lui a de lungime K, un vector a' = ( a_i1, a_i2 , ... , a_iK ) cu i₁ < i₂ < ... < i_K .

Cerinta

Sa se determine un subsir al lui a care este ordonat strict crescator si care are lungimea maxima.

Date de intrare

Fisierul de intrare scmax.in contine pe prima linie numarul N reprezentand numarul de elemente ale vectorului a . Pe cea de-a doua linie se afla N numere naturale reprezentand elementele vectorului a.

Date de iesire

In fisierul de iesire scmax.out se va afisa pe prima linie Lmax, avand semnificatia ca cel mai lung subsir crescator al sirului a are lungimea Lmax. Pe cea de-a doua linie se vor afla Lmax numere naturale reprezentand cel mai lung subsir crescator al vectorului a.

Restrictii

• 1 ≤ N ≤ 1000.
• 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.

Exemplu

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.

Cum se trimit solutii?