Revizia anterioară Revizia următoare
si rotatiile cu 90 de grade ale acestora.
Pentru a determina pentru fiecare configuratie solutia optima putem incerca orice impartire posibila cu doua linii in trei zone a dreptunghiului initial. Apoi ne trebuie pentru fiecare dreptunghi de tipul [1..i]x[1..j], [1..i][j..m], [i..n]x[1..j], [i..n]x[j..m], [i..j]x[1..m] si [1..n]x[i..j].
Ca sa determinam suma numerelor din un dreptunghi [r1..r2]x[c1..c2] folosim o matrice B[i][j] care e suma elementelor din [1..i]x[1..j], avand aceasta matrice calculata putem determina ca suma elementelor din dreptunghiul [r1..r2]x[c1..c2] este B[r2][c2] - B[r1 - 1][c2] - B[r2][c2 - 1] + B[r1 - 1][c1 - 1]. Pentru a calcula B[i][j] eficient parcurgem elementele matricii initiale A in ordine si avem ca B[i][j] = A[i][j] + B[i][j - 1] + B[i- 1][j] - B[i-1][j-1].
Vom explica cum determinam submatricea optima pentru dreptunghiul [i..j]x[1..m] in O(n), celelalte dreptunghiuri putand fi determinate intr-un mod asemanator. Avem trei cazuri posibile: linia de sus a dreptunghiului optim nu coincide cu linia i, si astfel putem lua informatia despre el din rezultatul calculului pentru dreptunghiul [i+1..j]x[1..m], al doilea caz e cand 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]
