Sous-matrice de somme maximale

Énoncé. On représente la « taille » d’une matrice par la somme de tous ses éléments. Étant donné une matrice carrée N × N, trouver la plus grande sous-matrice non vide (au moins 1 × 1) au sens de cette somme.

Par exemple, dans la matrice 4 × 4 suivante :

 0 -2 -7  0
 9  2 -6  2
-4  1 -4  1
-1  8  0 -2

La sous-matrice de somme maximale est :

9  2
-4 1
-1 8

Et sa somme vaut 15.

Approche. Une solution brute force explorant toutes les sous-matrices atteint une complexité trop élevée. On peut réduire le problème en fixant les lignes haute et basse de la sous-matrice, en compressant verticalement les colonnes comprises entre ces deux lignes, puis en appliquant l’algorithme de Kadane sur le tableau unidimensionnel obtenu.

Formellement, pour chaque paire de lignes (haut, bas), on construit le tableau :

colSum[c] = Σ mat[r][c] pour r de haut à bas.

Le maximum de somme contiguë de colSum correspond à la meilleure sous-matrice dont les lignes sont comprises entre haut et bas. On itère sur toutes les paires de lignes et on conserve le maximum global.

Implémentation en C++ :

#include <bits/stdc++.h>
using namespace std;

const int LIM = 105;
int n;
int tab[LIM][LIM];
int colSum[LIM];

int kadane(int vec[], int taille) {
    int meilleur = vec[0];
    int courant = vec[0];
    for (int i = 1; i < taille; ++i) {
        courant = max(vec[i], courant + vec[i]);
        meilleur = max(meilleur, courant);
    }
    return meilleur;
}

int main() {
    while (cin >> n) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> tab[i][j];

        int global = tab[0][0];
        for (int haut = 0; haut < n; ++haut) {
            fill(colSum, colSum + n, 0);
            for (int bas = haut; bas < n; ++bas) {
                for (int c = 0; c < n; ++c)
                    colSum[c] += tab[bas][c];
                int local = kadane(colSum, n);
                global = max(global, local);
            }
        }
        cout << global << endl;
    }
    return 0;
}

Remarque. L’initialisation de global ne peut pas être 0, car les valeurs de la matrice pouvant être négatives, le résultat pourrait aussi être négatif.

Sous-matrice de somme nulle

Énoncé. Trouver une sous-matrice dont la somme des éléments est exactement 0 et retourner les coordonnées des coins supéreiur gauche et inférieur droit.

Approche. On reprend le principe de compression. Pour chaque paire de lignes (haut, bas), on construit le tableau vertical[c] des sommes des colonnes entre ces deux lignes. Il reste alors à trouver un sous-tableau de vertical dont la somme est 0, ce que l’on fait à l’aide d’une table de hachage mémorisant les sommes cumulées déjà rencontrées.

Implémentation en Java :

import java.util.HashMap;

public class ZeroSubMatrix {
    public int[][] zeroSumSubmatrix(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) return new int[][]{{-1, -1}, {-1, -1}};
        int n = matrix[0].length;

        int[][] answer = new int[2][2];
        int[] vertical = new int[n];

        for (int top = 0; top < m; ++top) {
            for (int i = 0; i < n; ++i) vertical[i] = 0;
            for (int bottom = top; bottom < m; ++bottom) {
                for (int c = 0; c < n; ++c) {
                    vertical[c] += matrix[bottom][c];
                }
                HashMap<Integer, Integer> first = new HashMap<>();
                first.put(0, -1);
                int running = 0;
                for (int c = 0; c < n; ++c) {
                    running += vertical[c];
                    if (first.containsKey(running)) {
                        int left = first.get(running) + 1;
                        answer[0][0] = top;
                        answer[0][1] = left;
                        answer[1][0] = bottom;
                        answer[1][1] = c;
                        return answer;
                    }
                    first.put(running, c);
                }
            }
        }
        return answer;
    }
}