Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-02-28 19:41:52.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:scmax.in, scmax.outSursăad-hoc
AutorArhiva EducationalaAdăugată deFlorianFlorian Marcu Florian
Timp execuţie pe test0.15 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

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.inscmax.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?