${@+@}------{@+@}    {@+@}------{@+@}    {@+@}------{@+@}$
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]$.

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$).

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:

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;