Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-18 14:38:21.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
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: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(n2) zone, deci in total avem un algoritm ce consuma O(n2) memorie si are complexitatea O(n3) ca timp.
[I0] [IN ]
MN * [I1] = [IN+1]
[I2] [IN+2]
