| Fişierul intrare/ieşire: | subsecvm.in, subsecvm.out | Sursă | ad-hoc |
| Autor | Autor necunoscut | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Subsecventa de suma maxima
Se da un vector A de N numere intregi. Sa se determine subsecventa de suma maxima din acest vector, precum si suma elementelor acesteia. Printr-o subsecventa de limite i si j a unui vector de N elemente, cu 1 ≤ i ≤ j ≤ n, se intelege toate numerele cuprinse intre i si j.
Date de intrare
Fisierul de intrare subsecvm.in va contine doua linii. Pe prima linie se va afla numarul N, iar pe a doua linie se va afla un sir de N numere intregi.
Date de iesire
In fisierul de iesire subsecvm.out se vor afisa: pe prima linie doua numere reprezentand limitele subsecventei, iar pe a doua linie suma elementelor din subsecventa.
Restrictii si precizari
- 1 ≤ N ≤ 500 000
- -1 000 ≤ Ai ≤ 1 000, unde 1 ≤ i ≤ n
- Subsecventa de suma maxima va avea cel putin un element.
Exemplu
| subsecvm.in | subsecvm.out |
|---|---|
| 9 1 -4 5 -8 3 4 2 -1 10 | 5 9 18 |
Explicatie
Subsecventa de suma maxima este cuprinsa intre pozitiile 5 si 9, fiind formata din numerele 3; 4; 2; -1; 10. Suma acestor numere este 18.
Indicatii de rezolvare
Cea mai simpla rezolvare a acestei probleme este o solutie in O(N2), in care se fac sumele tuturor subsecventelor vectorului A, selectandu-se suma maxima. O solutie de 100 de puncte are complexitatea O(N), fiind bazata pe programarea dinamica.
