continue;
      } else if (sum >= bestSum) bestSum = sum;
}

==

==
 
h2(#prob2). Problema 2 ({_Maximum Sum_}) - 104 acm.uva.es
 
Se da o matrice de dimensiuni $NxN$ cu elemente intregi. Se cere determinarea unei submatrici a carei elemente au suma maxima.
 
h4. Exemplu
 
Pentru matricea<tex>\[ \left( \begin{array}{cccc}0 & -2 & -7 & 0 \\9 & 2 & -6 & 2 \\-4 & 1 & -4 & 1 \\-1 & 8 & 0 & -2 \end{array} \right)\]</tex>submatricea de sumă maximă este următoarea:<tex>\[ \left( \begin{array}{cc}9 & 2 \\-4 & 1 \\-1 & 8 \end{array} \right)\]</tex>
 
h3. Rezolvare
 
Putem folosi trucul construirii sumelor partiale prezentat in rezolvarea anterioara, pentru cazul *2D*. Pastram in $sum[i][j]$ suma tuturor elementelor $a[i{~1~}][j{~1~}]$ cu proprietatea ca $1 <= i{~1~} <= i$, si $1 <= j{~1~} <= j$. Putem calcula sumele prin metoda programarii dinamice (complexitate $O(N^2^)$) folosind formula $sum[i][j] = a[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]$. Acum pentru a calcula suma elementelor din matricea cu colturile $(i{~1~}, j{~1~}), (i{~2~}, j{~2~})$, unde $i{~1~} <= i{~2~} si j{~1~} <= j{~2~}$ este suficient sa facem calculul $sum[i{~2~}][j{~2~}] - sum[i{~1~}-1][j{~2~}] - sum[i{~2~}][j{~1~}-1] + sum[i{~1~}-1][j{~1~}-1]$. Astfel putem evalua suma din fiecare submatrice in timp constant, deci rezolvarea are ordinul de complexitate $O(N^4^)$.
O alta idee ar fi ca pentru fiecare pereche $(i{~1~}, i{~2~})$ fixate sa determinam perechea optima $(j{~1~}, j{~2~})$. Daca avem liniile $i{~1~}$ si $i{~2~}$ fixate atunci problema se transforma din una bidimensionala in una unidimensionala. Astfel pentru fiecare coloana $j$ vom considera $b[j]$ ca suma a elementelor $a[i][j]$ cu proprietatea ca $i{~1~} <= i <= i{~2~}$. In exemplul nostru daca $i{~1~} = 2$ si $i{~2~} = 3$, atunci avem $b{~1~} = 9 + (-4)$, $b{~2~} = 2 + 1$, $b{~3~} = (-6) + (-4)$ si $b{~4~} = 2 + 1$. Pentru a rezolva problema unidimensionala folosim unul din algoritmii liniari prezentati mai sus, astfel obtinandu-se un algoritm de complexitate totala $O(N^3^)$. Acest truc de a fixa doua linii pentru a transforma problema in una unidimensionala este util in multe probleme pe matrice sau cu puncte in plan.
Cel mai bun algoritm cunoscut pentru aceasta problema are complexitatea <tex>O(N^{3((\log \log N)/\log N)^{1/2}})</tex> si este mai mult un algoritm teoretic decat unul practic, usor implementabil.