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

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

h2. 'Culori':problema/culori