Analiza

Primetimo da ako smo izgradili ogradu čije je gornje levo polje ~(x,y)~, a donje desno je ~(z,t)~ mora da važi ~x\leq a\leq z~ i ~y\leq b\leq t~ da bi sadržalo polje koje sadrži kuću. Takođe vidimo da je u tom slučaju obim podmatrice upravo ~2\cdot(z+t-x-y)+4~. Sada vidimo da treba da maksmiziramo vrednost ~C_{xy}+C_{zt}+2\cdot(z+t-x-y)+4~, za ~x\leq a\leq z~ i ~y\leq b\leq t~. Prostom proverom po svim četvorkama daje lako ~O((NM)^2)~. Da bi se ovo dalje optimizovalo, izvršićemo zamenu redosleda sabiraka: treba da maksimiziziramo izraz ~(C_{xy}-2\cdot x-2\cdot y)+(C_{zt}+2\cdot z+2\cdot t)+4~. Označimo ~G_{xy}=C_{xy}-2\cdot x-2\cdot y~ i ~H_{zt}=C_{zt}+2\cdot z+2\cdot t~. Sada vidimo da tražimo maksimum ~G_{xy}+H_{zt}+4~, pri čemu važi ~x\leq a\leq z~, ~y\leq b \leq t~ i sabirci ~G_{xy}~ i ~H_{zt}~ su potpuno nezavisni. Stoga možemo da nađemo maksimum ~G_{xy}~ pod uslovom ~x\leq a, y\leq b~ (neka je ovaj maksimum ~M_1~) i maksimum ~H_{zt}~ po uslovom ~z\geq a, t\geq b~ (neka je ovaj maksimum ~M_2~), i zatim ispišemo rešenje ~M_1+M_2+4~. Računanje matrica ~G~ i ~H~, kao i traženje ~M_1~ i ~M_2~ se rade lakom pretragom u ~O(NM)~.