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