Submatricea cu suma maximă (Kadane 2D)

Am învățat algoritmul lui Kadane pe vectori - găsește secvența cu suma maximă în O(n). Acum extindem ideea la matrici: găsim submatricea (dreptunghiul de elemente consecutive) care are suma maximă.

Problema

Avem o matrice n x m cu elemente care pot fi pozitive și negative. Vrem să găsim submatricea (definită de colțul stânga-sus și colțul dreapta-jos) a cărei sumă de elemente este maximă.

Exemplu

Matrice 4 x 5:
 1 -2  3  4 -1
-3  5  2 -1  3
 4 -1  6  2 -5
-2  3 -4  1  2

Submatricea cu suma maximă este:

 5  2 -1
-1  6  2

Suma = 5 + 2 + (-1) + (-1) + 6 + 2 = 13

De ce nu funcționează forța brută?

Forța brută: încercăm toate submatricile posibile.

• Alegem colțul stânga-sus (r1, c1): O(n*m) variante
• Alegem colțul dreapta-jos (r2, c2): O(n*m) variante
• Calculăm suma: O(n*m) cu parcurgere sau O(1) cu sume parțiale 2D

Total: O(n² * m²) cu sume parțiale 2D - prea lent pentru matrici mari.

Ideea: reducem la Kadane 1D

Trucul este să fixăm două linii (r1 și r2) și să comprimăm matricea dintre ele într-un singur vector. Apoi aplicăm Kadane pe acel vector.

Pas cu pas

1. Fixăm linia de sus r1 și linia de jos r2.
2. Pentru fiecare coloană j, calculăm suma elementelor de pe coloana j între liniile r1 și r2. Punem rezultatul într-un vector col[j].
3. Aplicăm Kadane pe vectorul col - găsim secvența cu suma maximă.
4. Repetăm pentru toate perechile (r1, r2).

Matrice:                    r1=2, r2=3:
 1 -2  3  4 -1
-3 [5  2 -1  3]            col[1] = 5+(-1) = 4
 4 [-1 6  2 -5]            col[2] = 2+6 = 8
-2  3 -4  1  2             col[3] = -1+2 = 1
                            col[4] = 3+(-5) = -2

Kadane pe col = [4, 8, 1, -2]:
Secvența maximă: [4, 8, 1] = 13

Comprimarea coloanelor eficient

Nu recalculăm suma pe coloane de la zero pentru fiecare r2. O construim incremental:

• Când r2 crește cu 1, adăugăm linia r2 la vectorul col:

for (int j = 1; j <= m; j++)
    col[j] = col[j] + a[r2][j];

Costul: O(m) per linie adăugată.

Codul complet

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[301][301];
int col[301];
int n, m;

int kadane(int v[], int lung) {
    int maxSuma = v[1];
    int sumaCurenta = 0;

    for (int i = 1; i <= lung; i++) {
        sumaCurenta = sumaCurenta + v[i];
        if (sumaCurenta > maxSuma)
            maxSuma = sumaCurenta;
        if (sumaCurenta < 0)
            sumaCurenta = 0;
    }

    return maxSuma;
}

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            fin >> a[i][j];

    int rezultat = a[1][1];

    for (int r1 = 1; r1 <= n; r1++) {
        // Resetăm vectorul de coloane
        for (int j = 1; j <= m; j++)
            col[j] = 0;

        for (int r2 = r1; r2 <= n; r2++) {
            // Adăugăm linia r2
            for (int j = 1; j <= m; j++)
                col[j] = col[j] + a[r2][j];

            // Kadane pe col
            int sumaMax = kadane(col, m);
            if (sumaMax > rezultat)
                rezultat = sumaMax;
        }
    }

    fout << rezultat;

    return 0;
}

date.in:

4 5
1 -2 3 4 -1
-3 5 2 -1 3
4 -1 6 2 -5
-2 3 -4 1 2

date.out:

13

Complexitate

• Fixăm r1: O(n) variante
• Fixăm r2: O(n) variante (de la r1 la n)
• Kadane pe col: O(m)
• Total: O(n² * m)

Exemplu detaliat

Matrice 3 x 4:
 2 -1  3 -2
 4  5 -3  1
-1  2  6 -4

r1 = 1

r1 = 2

r1 = 3

Rezultat: 17 (submatricea liniile 1-3, coloanele 1-3)

Varianta cu pozițiile submatricei

Dacă vrem și coordonatele submatricei, le salvăm în Kadane:

int kadane(int v[], int lung, int &cSt, int &cDr) {
    int maxSuma = v[1];
    int sumaCurenta = 0;
    int tempSt = 1;
    cSt = 1;
    cDr = 1;

    for (int i = 1; i <= lung; i++) {
        sumaCurenta = sumaCurenta + v[i];
        if (sumaCurenta > maxSuma) {
            maxSuma = sumaCurenta;
            cSt = tempSt;
            cDr = i;
        }
        if (sumaCurenta < 0) {
            sumaCurenta = 0;
            tempSt = i + 1;
        }
    }

    return maxSuma;
}

Și în main salvăm r1, r2, cSt, cDr:

int bestR1, bestR2, bestCSt, bestCDr;
int rezultat = a[1][1];

for (int r1 = 1; r1 <= n; r1++) {
    for (int j = 1; j <= m; j++) col[j] = 0;

    for (int r2 = r1; r2 <= n; r2++) {
        for (int j = 1; j <= m; j++)
            col[j] = col[j] + a[r2][j];

        int cSt, cDr;
        int sumaMax = kadane(col, m, cSt, cDr);
        if (sumaMax > rezultat) {
            rezultat = sumaMax;
            bestR1 = r1;
            bestR2 = r2;
            bestCSt = cSt;
            bestCDr = cDr;
        }
    }
}

fout << "Suma: " << rezultat << endl;
fout << "De la (" << bestR1 << "," << bestCSt << ") la (" << bestR2 << "," << bestCDr << ")" << endl;

Submatricea de 1-uri cu aria maximă

O variantă frecventă: avem o matrice binară (0 și 1) și vrem cel mai mare dreptunghi format doar din 1-uri.

Aceasta se rezolvă diferit (cu histogramă pe fiecare linie), dar ideea de a comprima linii se păstrează.

Matrice:          h:
1 0 1 1           1 0 1 1
1 1 1 0           2 1 2 0
0 1 1 1           0 2 3 1

Când n < m?

Algoritmul are complexitate O(n² * m). Dacă n > m, putem transpune matricea ca n să fie dimensiunea mai mică - obținem O(min(n,m)² * max(n,m)).

if (n > m) {
    // transpunem matricea
    // swap n, m
}

Greșeli frecvente

1. Kadane cu inițializare greșită

int maxSuma = 0; // GREȘIT dacă toate elementele sunt negative
int maxSuma = v[1]; // CORECT

Dacă toate elementele sunt negative, maximul e cel mai mare element negativ, nu 0.

2. Uitarea resetării vectorului col

// La fiecare r1 nou, col trebuie resetat la 0
for (int j = 1; j <= m; j++)
    col[j] = 0;

3. Confuzia n cu m

• r1, r2 merg de la 1 la n (linii)
• j merge de la 1 la m (coloane)
• Kadane se aplică pe m elemente (lungimea vectorului col)

Ce să reții

• Kadane 2D reduce problema la Kadane 1D fixând două linii și comprimând coloanele.
• Complexitate: O(n² * m) - mult mai bun decât O(n² * m²).
• Vectorul col[j] se construiește incremental - adăugăm câte o linie.
• Kadane pe col: secvența cu suma maximă = coloanele submatricei optime.
• Funcționează cu elemente negative (spre deosebire de alte tehnici).
• Dacă n > m, transpunem matricea pentru performanță optimă.

Probleme

pbinfoSubmatrixsummax→