${@+@}------{@+@}    {@+@}------{@+@}    {@+@}------{@+@}$
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..r~2~]x[c1..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]$.

Ca sa determinam suma numerelor din un dreptunghi $[r{~1~}..r{~2~}]x[c1..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$).