== 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

h2. Restricţii

* $1 ≤ N ≤ 5 000 000$
* $|S{~i~}| ≤ 1 000$

* $1 ≤ N ≤ 6 000 000$

* Pentru $20%$ dintre teste: $1 ≤ N ≤ 1 000$.

* Pentru încă $20%$: $5 000 ≤ N ≤ 50 000$.
* Pentru restul de $60%$: $100 000 ≤ N ≤ 5 000 000$.

* Pentru încă $20%$: $5 000 ≤ N ≤ 30 000$.
* Pentru restul de $60%$: $100 000 ≤ N ≤ 6 000 000$.

* Dacă există mai mult 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.

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$ subsecvenţe ce se pot forma.
 
h2. Indicaţii de rezolvare
 
Un articol excelent care tratează această problemă şi numeroase alte probleme cu secvenţe se găseşte 'la această adresă':probleme-cu-secvente#problema-1.
 
Soluţia cea mai simplă constă în fixarea celor doi indici, de început şi de sfârşit, şi calcularea sumei pe acest interval. 'Soluţia':job_detail/257843?action=view-source are complexitatea $O(N^3^)$ şi obţine $20p$.
 
Dacă fixăm începutul secvenţei iar în timp ce iterăm cu al doilea indice calculăm şi suma secvenţei, obţinem o 'soluţie':job_detail/257844?action=view-source în complexitate $O(N^2^)$ ce obţine $40p$.
 
Volumul mare de date permite 'acestei soluţii':job_detail/257845?action=view-source să obţină $70-85p$ în complexitate $O(N*log(N))$, depinzând de tipul funcţiilor folosite pentru citirea datelor. Recomandăm folosirea streamurilor din C++ în locul funcţiilor de citire din librăria limbajului C. Soluţia foloseşte metoda _Divide et Impera_. Un interval $[i, j]$ îl împărţim în două: $[i, mid]$ şi $[mid + 1, j]$ unde $mid = (i + j) / 2$, calculăm subsecvenţa de sumă maximă în cele două intervale şi apoi le combinăm prin alegerea unei subsecvenţe care este suma dintre subsecvenţa de sumă maximă ce se termină pe poziţia $mid$ în intervalul $[i, mid]$ şi a celei care începe pe poziţia $mid + 1$ în intervalul $[mid + 1, j]$.
 
'Prima soluţie':job_detail/257848?action=view-source ce obţine $100p$ în complexitate $O(N)$ foloseşte următoarea idee: notând cu $S{~i~}$ suma tuturor valorile din şir de pe poziţiile $1 .. i$ atunci suma maximă a unei subsecvenţe ce se termină pe poziţia $i$ este $Max(S{~i~} - S{~j~}), j < i$ care este echivalentă cu $S{~i~} - Min(S{~j~}), j < i$. Rezultă că va trebui doar să reţinem minimul dintre toate sumele parţiale $S{~j~}$ cu $j < i$.
 
'Cea de a doua soluţie':job_detail/257847?action=view-source ce obţine $100p$ foloseşte metoda _Programării dinamice_. Construim un şir $best{~i~}$ egal cu costul subsecvenţei de sumă maximă ce se termină pe poziţia $i$. Rezultă recurenţa următoare: $best{~i~} = Max(best{~i-1~} + s{~i~}, s{~i~})$. Rezultă mai departe că $s{~i~}$ este sfârşitul unei subsecvenţe ce se extinde spre stânga cu subsecvenţa de sumă maximă ce se termină în $s{~i-1~}$ doar dacă această subsecvenţă are suma pozitivă. În implementare nu este necesar să reţinem întregul vector $best$, ci doar o variabilă, după cum se vede şi în sursă. Complexitate: $O(N)$.
 
Multe dintre soluţiile de mai sus pot fi rezolvate cu $O(1)$ memorie. 'Iată un exemplu':job_detail/257846?action=view-source pentru a doua soluţie de $100p$.
 
h2. Probleme suplimentare
 
* 'Maximum Sum':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44, _UVa_
* 'Joctv':problema/joctv
* 'Oraşe':problema/orase
* 'Secvenţa 2':problema/secv2
* 'Peri':problema/peri
* 'Cârnaţi':problema/carnati
* 'TreiD':problema/TreiD

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

3667