}
==

h2(#prob2). Problema 2 ({_Maximum Sum_}) - 104 acm.uva.es

h2(#prob2). Problema 2 ( "_Maximum Sum_":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44 )

Se da o matrice de dimensiuni $NxN$ cu elemente intregi. Se cere determinarea unei submatrici a carei elemente au suma maxima.

Se dă o matrice de dimensiuni $NxN$ cu elemente întregi. Se cere determinarea unei submatrici a cărei elemente au suma maximă.

h4. Exemplu

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.

Putem folosi trucul construirii sumelor parţiale din rezolvarea anterioară, pentru cazul *2D*. Păstrăm în $sum[i][j]$ suma tuturor elementelor $a[i{~1~}][j{~1~}]$ cu proprietatea că $1 <= i{~1~} <= i$, şi $1 <= j{~1~} <= j$. Putem calcula sumele prin metoda programării 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 colţurile $(i{~1~}, j{~1~})$ şi $(i{~2~}, j{~2~})$, unde $i{~1~} <= i{~2~}$ şi $j{~1~} <= j{~2~}$, este suficient să 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 în timp constant, deci rezolvarea are ordinul de complexitate $O(N^4^)$.
 
O altă idee ar fi ca pentru fiecare pereche $(i{~1~}, i{~2~})$ fixată să determinăm perechea optimă $(j{~1~}, j{~2~})$. Dacă avem liniile $i{~1~}$ şi $i{~2~}$ fixate atunci problema se transformă din una bidimensională în una unidimensională. Astfel pentru fiecare coloană $j$ vom considera $b[j]$ ca sumă a elementelor $a[i][j]$ cu proprietatea că $i{~1~} <= i <= i{~2~}$. În exemplul nostru, dacă $i{~1~} = 2$ şi $i{~2~} = 3$, atunci avem $b{~1~} = 9 + (-4)$, $b{~2~} = 2 + 1$, $b{~3~} = (-6) + (-4)$ şi $b{~4~} = 2 + 1$. Pentru a rezolva problema unidimensională folosim unul din algoritmii liniari prezentaţi mai sus, astfel obţinându-se un algoritm de complexitate totală $O(N^3^)$. Acest truc de a fixa două linii pentru a transforma problema în una unidimensională este util în multe probleme pe matrice sau cu puncte în plan.
 
Cel mai bun algoritm cunoscut pentru această problemă are complexitatea <tex>O(N^{3\sqrt{\frac{\log \log N}{\log N}}})</tex> si este mai mult un algoritm teoretic decat unul practic, usor implementabil.

h2(#prob3). Problema 3 ({_Interogare_}) - Bursele Agora 2005/2006 Runda 1