== include(page="template/taskheader" task_id="ssm") ==

Se dă un şir $S[] = (s{~1~}, s{~2~}, .., s{~N~})$ de lungime $N$. O subsecvenţă a şirului este de forma $(s{~i~}, s{~i+1~}, ..., s{~j~})$, cu $1 ≤ i ≤ j ≤ N$. Suma subsecvenţei este $s{~i~} + s{~i+1~} + ... + s{~j~}$.

Se dă un şir $S[] = (s{~1~}, s{~2~}, .., 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~}$.

h2. Cerinţă

h2. Date de intrare

Fişierul de intrare $ssm.in$ conţine pe prima linie un număr natural $N$, reprezentând lungimea şirului. Pe următoarea linie se găsesc $N$ numere întregi separate printr-un spaţiu, reprezentând în ordine elementele şirului.

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.

h2. Date de ieşire

h3. 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$ secvenţe ce se pot forma.
 
h2. Indicaţii de rezolvare
 
Un articol excelent care tratează această problemă şi numeroase altele cu secvenţe se găseşte 'la această adresă':probleme-cu-secvente#problema-1.
 
h2. Probleme suplimentare
 
Problemele de mai jos se reduc la găsirea subsecvenţei de sumă maximă, dar restricţiile impuse asupra secvenţei necesită uneori folosirea unei structuri de date numită deque. Mai multe informaţii despre această structură găsiţi 'la această adresă':deque-si-aplicatii.
 
* 'Maximum Sum':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44, _UVa_
* 'Sum 2':problema/sum2, _Stelele Informaticii_
* 'Secvenţă 2':problema/secv2
* 'Secvenţă 3':problema/secv3
* 'Secvenţă 4':problema/secv4

== include(page="template/taskfooter" task_id="ssm") ==