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 $[r{~1~}..r{~2~}]x[c{~1~}..c{~2~}]$ 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 $[r{~1~}..r{~2~}]x[c{~1~}..c{~2~}]$ este {$B[r{~2~}][c{~2~}] - B[r{~1~} - 1][c{~2~}] - B[r{~2~}][c{~2~} - 1] + B[r{~1~} - 1][c{~1~} - 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:

== 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  ~}]