Această problemă reprezintă o extindere în două dimensiuni a problemei anterioare 'Vila 2':deque-si-aplicatii#problema-2, unde am studiat cazul unidimensional al determinării pe un vector a maximului / minimului pentru fiecare subsecvenţă de o lungime fixată.

Cerinţa constă în amplasarea unui dreptunghi $R x C$ astfel încât valoarea maximă din interiorul său să fie cât mai mică. Una din ideile simple constă în fixarea colţului din stânga sus în toate cele $(M - R) x (N - C)$ poziţii şi determinarea maximului din interiorul său cu o altă parcurgere a celor $R x C$ elemente. Dar, să fixăm o linie $i$. Atunci, pentru a fixa colţul din stânga sus mai iterăm cu un indice $j$ între coloanele $1$ şi $N-C+1$. De aici devine clar că atunci când avansăm indicele coloanei în dreptunghiul curent apare o nouă coloană, $j + C$, şi dispare coloana curentă $j$. Dacă pentru fiecare coloană $j$ de pe linia curentă $i$ reţinem un $Max{~i,j~}$ egal cu maximul dintre elementele $P{~i,j~}, P{~i+1,j~},.. P{~i+R-1,j~}$, atunci pe linia fixată $i$ vom avea un vector din $N$ elemente (numărul de coloane al matricei $P$) alcătuit din valorile $Max{~i,1~}, Max{~i,2~}, Max{~i,3~},.. Max{~i,j~},.. Max{~i,N-1~}, Max{~i,N~}$. Iar pe acest vector va trebui să determinăm pentru fiecare subsecvenţă de $C$ elemente, valoarea maximă. Dintre toate subsecvenţele o vom alege pe cea cu valoarea maximă cea mai mică. Iar acest rezultat va fi o soluţie pentru linia fixată. Cu valorile din $Max$ precalculate, pentru fiecare linie avem complexitatea $O(N)$, deci $O(M * N)$ pentru întreaga matrice. Însă, implementând direct, valorle din $Max$ se calculează în $O(M * N * R)$. Mai sus am definit $Max{~i,j~}$ ca fiind maximul dintre $P{~i,j~}, P{~i+1,j~},.. P{~i+R-1,j~}$. Rezultă că $Max{~i+1,j~}$ este maximul dintre $P{~i+1,j~}, P{~i+2,j~},.. P{~i+R-1,j~}, P{~i+R,j~}$, adică maximul dintre elementele lui $Max{~i,j~}$ din care scoatem $P{~i,j~}$ şi adăugăm $P{~i+R,j~}$. De aici deducem că pentru fiecare coloană fixată, valorile lui $Max$ de pe coloana respectivă se reduc la a determina pentru fiecare subsecvenţă de lungime $R$ (numărul de linii al dreptunghiului de amplasat) elementul maxim. Aceste rezultate se obţin în $O(M)$ pentru fiecare coloană, deci $O(N * M)$ în total.

Cerinţa constă în amplasarea unui dreptunghi $R x C$ astfel încât valoarea maximă din interiorul său să fie cât mai mică. Una din ideile simple constă în fixarea colţului din stânga sus în toate cele $(M - R + 1) x (N - C + 1)$ poziţii şi determinarea maximului din interiorul său cu o altă parcurgere a celor $R x C$ elemente. Dar, să fixăm o linie $i$. Atunci, pentru a fixa colţul din stânga sus mai iterăm cu un indice $j$ între coloanele $1$ şi $N - C + 1$. De aici devine clar că atunci când avansăm indicele coloanei în dreptunghiul curent apare o nouă coloană, $j + C$, şi dispare coloana $j$. Dacă pentru fiecare coloană $j$ de pe linia curentă $i$ reţinem un $Max{~i,j~}$ egal cu maximul dintre elementele $P{~i,j~}, P{~i+1,j~},.. P{~i+R-1,j~}$, atunci pe linia fixată $i$ vom avea un vector din $N$ elemente (numărul de coloane al matricei $P$) alcătuit din valorile $Max{~i,1~}, Max{~i,2~}, Max{~i,3~}, ..., Max{~i,j~}, ..., Max{~i,N-1~}, Max{~i,N~}$. Iar pe acest vector va trebui să determinăm pentru fiecare subsecvenţă de $C$ elemente, valoarea maximă. Dintre toate subsecvenţele o vom alege pe cea cu valoarea maximă cea mai mică. Iar acest rezultat va fi o soluţie pentru linia fixată. Cu valorile din $Max$ precalculate, pentru fiecare linie avem complexitatea $O(N)$, deci $O(M * N)$ pentru întreaga matrice. Însă, implementând direct, valorile din $Max$ se calculează în $O(M * N * R)$. Mai sus am definit $Max{~i,j~}$ ca fiind maximul dintre $P{~i,j~}, P{~i+1,j~}, ..., P{~i+R-1,j~}$. Rezultă că $Max{~i+1,j~}$ este maximul dintre $P{~i+1,j~}, P{~i+2,j~}, ..., P{~i+R-1,j~}, P{~i+R,j~}$, adică maximul dintre elementele lui $Max{~i,j~}$ din care scoatem $P{~i,j~}$ şi adăugăm $P{~i+R,j~}$. De aici deducem că pentru fiecare coloană fixată, valorile lui $Max$ de pe coloana respectivă se reduc la a determina pentru fiecare subsecvenţă de lungime $R$ (numărul de linii al dreptunghiului de amplasat) elementul maxim. Aceste rezultate se obţin în $O(M)$ pentru fiecare coloană, deci $O(N * M)$ în total.

Rezultă complexitatea finală $O(M * N)$.