Pentru a determina subsecventa de suma maxima a sirului $C$, vom folosi vectorul $sum[k] = C[k] + C[k-1] + ... + C[1]$. Astfel suma elementelor $C[k..l]$ este egala cu $sum[l] - sum[k - 1]$. Pentru a determina subsecventa de suma maxima ce se termina in $l$ trebuie sa gasim cea mai mica $sum[k - 1]$ pentru a maximiza expresia $sum[l] - sum[k - 1]$. Astfel obtinem urmatorul cod:

== code(c) |

int min_sum = 0;

int best = - infinit;
for (int k = 0; k < m; k++) {

    if (best < sum[l] - min_sum)
        best = sum[l] - min_sum;
    if (sum[l] < min_sum) min_sum = sum[l];

 
if (best < sum[l] - min_sum)
 
best = sum[l] - min_sum;
 
if (sum[l] < min_sum) min_sum = sum[l];
 

}
return best;

==
Acest algoritm are complexitatea $O(n)$.

Acest algoritm are complexitatea O(n).
 
Astfel algoritmul calculeaza in O(n) valoarea optima pentru O(n^2) zone, deci in total avem un algoritm ce consuma O(n^2) memorie si are complexitatea O(n^3) ca timp.
 
References
 
Visible links
1. http://infoarena.devnet.ro/index.php?page=read&conid=arhiva&tid=bmatrix

Astfel algoritmul calculeaza in $O(n)$ valoarea optima pentru $O(n^2)$ zone, deci in total avem un algoritm ce consuma $O(n^2)$ memorie si are complexitatea $O(n^3)$ ca timp.