O prima idee de solutie ar fi sa construim o matrice $A[i][j][k]$ = elementul de valoare maxima dintr-un patrat cu coltul stanga-sus pe linia $i$ si coloana $j$ si latura $k$. Aceasta  matrice se poate calcula in $O(N^3^)$ astfel:
$A[i][j][k] = max(A[i][j][k-1], A[i+1][j][k-1], A[i][j+1][k-1], A[i+1][j+1][k-1])$
Fiecare intrebare poate fi rezolvata in $O(1)$, dar constructia matricei $A$ nu se va incadra in timp pentru testele mari.

Problema poate fi consideranta o varianta clasica a problemei de $RMQ$ in $2D$. Un articol foarte detaliat (in engleza) despre problema $RMQ$ gasiti 'aici':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor. Asadar, pentru a rezolva cazul $2D$ vom folosi ideile care se folosesc in rezolvarea cazului $1D$. Astfel, vom calcula matricea $A$ dar doar pentru laturi puteri ale lui $2$. $A[i][j][k]$ va fi elementul de valoare maxima dintr-un patrat cu coltul stanga-sus pe linia $i$ si coloana $j$ si latura $2^k^$.

Problema poate fi consideranta o varianta clasica a problemei de $RMQ$ in $2D$. Un articol foarte detaliat (in engleza) despre problema $RMQ$ gasiti 'aici':https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/. Asadar, pentru a rezolva cazul $2D$ vom folosi ideile care se folosesc in rezolvarea cazului $1D$. Astfel, vom calcula matricea $A$ dar doar pentru laturi puteri ale lui $2$. $A[i][j][k]$ va fi elementul de valoare maxima dintr-un patrat cu coltul stanga-sus pe linia $i$ si coloana $j$ si latura $2^k^$.

$A[i][j][k] = max(A[i][j][k-1], A[i][j+2^k-1^][k-1], A[i+2^k-1^][j][k-1], A[i+2^k-1^][j+2^k-1^][k-1])$
Pentru o raspunde la o intrebare $i j k$ in $O(1)$ vom determina cea mai mare putere $p$ a lui $2$ astfel incat $2^p^ ≤ k$, si vom lua maximul din $4$ patrate cu colturile in patratul din intrebare si latura $2^p^$. Astfel, raspunsul pentru o intrebare $i j k$ este $max(A[i][j][p], A[i][j+k-2^p^][p], A[i+k-2^p^][j][p], A[i+k-2^p^][j+k-2^p^][p])$.