Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-18 14:37:39.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
linia de jos nu coincide cu linia j, acum luam rezultatul optim pentru dreptunghiul [i..j-1]x[1..m]. Al treilea caz cand dreptunghiul optim se sprijina pe liniile i si j il putem rezolva in O(n) asemanator problemei de determinare a unei subsecvente de suma maxima pe un vector C. C[k] va fi egal cu suma elementelor din dreptunghiul [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]
