Feel free to play around.

a {$[i..j] x [k..k]$} (deci suma elementelor din banda {$[i..j]$} ce sunt pe coloana {$k$}).
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];
}
return best;
==
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.
 
p(pre).
     [I{~0~}]    [I{~N&nbsp;&nbsp;~}]
M^N^ * [I{~1~}] = [I{~N+1~}]
     [I{~2~}]    [I{~N+2~}]
 
 
== Gallery(page="%" file="%.jpg") ==
 
== Gallery(page="%" file="%.gif") ==
 
== Gallery(page="%" file="%.png") ==
 

gigi  strong. ionel</strong>