(Creat de ==user(user="ditzonec" type="tiny")== la data de _2006-08-11_ categoria _Competitii_, autor(i) _Adrian Diaconu si Cosmin Negruseri_)

 ==Include(page="template/raw")==
 

h2. Sah
Prima observatie ar fi ca pentru a ne asigura ca intr-o regiune numarul de casute albe este egal cu numarul de celule negre este suficient ca aria regiunii sa fie para.

Vom explica cum determinam submatricea optima pentru dreptunghiul $[i..j]x[1..m]$ in $O(n)$, celelalte dreptunghiuri putand fi determinate intr-un mod asemanator. Avem trei cazuri posibile: linia de sus a dreptunghiului optim nu coincide cu linia $i$, si astfel putem lua informatia despre el din rezultatul calculului pentru dreptunghiul $[i+1..j]x[1..m]$, al doilea caz e cand linia de jos nu coincide cu linia $j$, acum luam rezultatul optim pentru dreptunghiul $[i..j-1]x[1..m]$. Al treilea caz cand dreptunghiul optim se sprijina pe liniile $i$ si $j$ il putem rezolva in $O(n)$ asemanator problemei de determinare a unei subsecvente de suma maxima pe un vector $C$. $C[k]$ va fi egal cu suma elementelor din dreptunghiul $[i..j] x [k..k]$ (deci suma elementelor din banda $[i..j]$ ce sunt pe coloana $k$).
Pentru a determina subsecventa de suma maxima a sirului $C$, vom folosi vectorul $sum[k] = C[k] + C[k-1] + ... + C[1]$. Astfel suma elementelor $C[k..l]$ este egala cu $sum[l] - sum[k - 1]$. Pentru a determina subsecventa de suma maxima ce se termina in $l$ trebuie sa gasim cea mai mica $sum[k - 1]$ pentru a maximiza expresia $sum[l] - sum[k - 1]$. Astfel obtinem urmatorul cod:

== code(c) |
int min_sum = 0;
int best = - infinit;

for (int k = 0; k < m; k++) {
    if (best < sum[l] - min_sum)
        best = sum[l] - min_sum;
    if (sum[l] < min_sum) min_sum = sum[l];
}

return best;
==

Acest algoritm are complexitatea $O(n)$.

Astfel algoritmul calculeaza in $O(n)$ valoarea optima pentru $O(n^2)$ zone, deci in total avem un algoritm ce consuma $O(n^2)$ memorie si are complexitatea $O(n^3)$ ca timp.