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 ≤ 100 000
- 1 ≤ ai ≤ 2 000 000 000 , pentru orice i de la $1$ la 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 |
Indicatii de rezolvare
Problema se rezolva folosind programarea dinamica. Se noteaza besti - lungimea maxima a unui subsir crescator care se termina pe pozitia i . Obtinem astfel urmatoarea relatie: besti = max ( 1 , max ( aj) + 1) cu 1 ≤ j < i si aj < ai . Pentru a reconstrui solutia mai retinem un vector cu semnificatia prei - 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 Lj unde 1 ≤ j < i astfel incat aj ≤ ai. 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 .
