Fișierul intrare/ieșire	ssm.in, ssm.out	Sursă	Infoarena
Autor	teorie	Adăugată de	Marcela • Marcela
Timp de execuție pe test	0.8 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Subsecvenţa de sumă maximă

Se dă un șir S[ ] = (s₁, s₂, ..., s_N) de lungime N . O subsecvență a șirului este de forma: (s_i, s_i+1, ..., s_j) cu 1 ≤ i ≤ j ≤ N, iar suma subsecvenței este s_i + s_i+1 + ... + s_j.

Cerință

Se cere să se determine subsecvența de sumă maximă.

Date de intrare

Fișierul de intrare ssm.in conține pe prima linie un număr natural N, reprezentând lungimea șirului. Următoarea linie conține N numere întregi separate printr-un spațiu, reprezentând în ordine elementele șirului.

Date de ieșire

În fișierul de ieșire ssm.out se vor tipări trei numere în această ordine: suma subsecvenței de sumă maximă, indicele de început și indicele de sfârșit.

Restricții

• 1 ≤ N ≤ 6 000 000
• Pentru 20% dintre teste: 1 ≤ N ≤ 1 000
• Pentru încă 20% dintre teste: 5 000 ≤ N ≤ 30 000
• Pentru restul de 60%: 100 000 ≤ N ≤ 6 000 000
• Dacă există mai multe subsecvențe candidate la soluție, atunci se va tipări cea cu indicele de început cel mai mic, iar în caz de egalitate cea mai scurtă.
• Se garantează că toate rezultatele intermediare și cel final vor putea fi reprezentate pe întregi cu semn pe 32 de biți.

Exemplu

Explicație

Subsecvența de sumă maximă este: (3, 4, -2, 3), a cărei sumă 3 + 4 – 2 + 3 = 8 este maximă dintre toate cele N *( N-1 )/ 2 subsecvențe ce se pot forma.