h2. Restricţii

* $1 ≤ N ≤ 7 000 000$

* $1 ≤ N ≤ 6 000 000$

* Pentru $20%$ dintre teste: $1 ≤ N ≤ 1 000$.
* Pentru încă $20%$: $5 000 ≤ N ≤ 30 000$.

* Pentru restul de $60%$: $100 000 ≤ N ≤ 7 000 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.

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

'O soluţie':job_detail/257845?action=view-source ce obţine $70p$ are complexitatea $O(N*log(N))$ şi 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$ are la bază următoarea idee: elementul de pe poziţia $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ă. Complexitate: $O(N)$.

 
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

3667