==
O prezentare detaila a acestei probleme si metode de rezolvare gasiti 'aici':http://www.ginfo.ro/revista/11_2/focus2.pdf.

Vom trata acum si faptul ca sirul este circular. Astfel, trebuie verificate si secventele de forma $i,i+1,...N-1,N,1,2,...j-1,j$. Pentru a realiza acest lucru eficient precalculam un sir de sume partiale $S{~i~} = A{~1~} + A{~2~} + ... + A{~i~} = S{~i-1~}+A{~i~}$ si un al doilea sir $T{~i~} = max(S{~1~}, S{~2~},..., S{~i~}) = max(T{~i-1~}, S{~i~})$. Pentru un $i$ fixat, cea mai buna secventa de forma $i,i+1,...N-1,N,1,2,...j-1,j$ se poate calcula in $O(1)$ astfel: $T{~i-1~}+S{~N~}-S{~i-1~}$. Complexitatea rezolvarii este $O(N)$, iar pentru reconstituirea solutiei sunt necesare  doar cateva variabile aditionale pentru pozitie si lungime.

Vom trata acum si faptul ca sirul este circular. Astfel, trebuie verificate si secventele de forma $i,i+1,...N-1,N,1,2,...j-1,j$. Pentru a realiza acest lucru eficient precalculam un sir de sume partiale $S{~i~} = A{~1~} + A{~2~} + ... + A{~i~} = S{~i-1~}+A{~i~}$ si un al doilea sir $T{~i~} = max(S{~1~}, S{~2~},..., S{~i~}) = max(T{~i-1~}, S{~i~})$. Pentru un $i$ fixat, cea mai buna secventa de forma $i,i+1,...N-1,N,1,2,...j-1,j$ se poate calcula in $O(1)$ astfel: $T{~i-1~}+S{~N~}-S{~i-1~}$.
 
Un alt mod de a verifica secventele de forma $i,i+1,...N-1,N,1,2,...j-1,j$ este daca observam ca suma acestei secvente este de fapt suma tuturor elementelor din care se scade secventa $j+1, j+2, ... i-2, i-1$. Astfel ne intereseaza o secventa de suma minima pe care sa o scadem din suma totala. Aceasta se poate determina cu o mica modificare a alogirtmului pentru suma maxima sau inmultind elementele cu $-1$ si cautand o secventa de suma maxima.
 
Complexitatea rezolvarii este $O(N)$, iar pentru reconstituirea solutiei sunt necesare  doar cateva variabile aditionale pentru pozitie si lungime.

h2. 'Zero 2':problema/zero2