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

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