Revizia anterioară Revizia următoare
| 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' = ( ai1, ai2 , ... , aiK ) cu i1 < i2 < ... < iK .
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 ≤ ai ≤ 50000 , 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
| scmax.in | scmax.out |
|---|---|
| 5 24 12 15 15 19 | 3 12 15 19 |
Explicatie
Feedback(Cosmin): Nu punem si solutia in O(n log n)?
Raspuns(Florian): Din pacate nu stiu solutia in NlogN. Dar daca imi spui ideea cred ca ma prind. Si vedem ce putem face.
Cosmin: 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.
Florian: Parearea mea e ca se complica putin lucrurile si problema nu mai e dinamica pura. Insa, daca e neaparata nevoie, voi mari N-ul ca sa nu intre in timp O(n^2).
