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

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

'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{~i~}$, 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$.