h2. Restricţii

* $1 ≤ N ≤ 5 000 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.

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/257569?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/257568?action=view-source în complexitate $O(N^2^)$ ce obţine $40p$.
'Prima soluţie':job_detail/257566?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/257567?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)$.
'Cea de a treia soluţie':job_detail/257573?action=view-source ce obţine $100p$ 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]$.
Multe dintre soluţiile de mai sus pot fi rezolvate cu $O(1)$ memorie. 'Iată un exemplu':job_detail/257620?action=view-source pentru a doua soluţie de $100p$.

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

h2. Probleme suplimentare

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

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.

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

* 'TreiD':problema/TreiD
* 'Cârnaţi':problema/carnati

* 'Secvenţa 2':problema/secv2

* 'Peri':problema/peri

* 'Cârnaţi':problema/carnati
* 'TreiD':problema/TreiD

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

3667