Encontrar la submatriz de ceros más grande

Se da una matriz con n filas y m columnas. Encontrar la submatriz más grande que consiste solo de ceros (una submatriz es un área rectangular de la matriz).

Algoritmo

Los elementos de la matriz serán a[i][j], donde i = 0...n - 1, j = 0... m - 1. Por simplicidad, consideraremos todos los elementos no nulos iguales a 1.

Paso 1: Dinámica auxiliar

Primero calculamos la siguiente matriz auxiliar: d[i][j], la fila más cercana que tiene un 1 por encima de a[i][j]. Formalmente, d[i][j] es el mayor número de fila (de 0 a i - 1) en el que hay un elemento igual a 1 en la columna j. Mientras iteramos de arriba-izquierda a abajo-derecha, cuando estamos en la fila i, conocemos los valores de la fila anterior, así que alcanza con actualizar solo los elementos con valor 1. Podemos guardar los valores en un arreglo simple d[i], i = 1...m - 1, porque en el algoritmo posterior procesaremos la matriz una fila a la vez y solo necesitamos los valores de la fila actual.

vector<int> d(m, -1);
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        if (a[i][j] == 1) {
            d[j] = i;
        }
    }
}

Paso 2: Resolver el problema

Podemos resolver el problema en $O(n m^2)$ iterando por filas, considerando cada posible columna izquierda y derecha de una submatriz. El fondo del rectángulo será la fila actual, y usando d[i][j] podemos encontrar la fila de arriba. Sin embargo, es posible ir más lejos y mejorar significativamente la complejidad de la solución.

Está claro que la submatriz de ceros deseada está acotada en los cuatro lados por unos, que le impiden crecer y mejorar la respuesta. Por lo tanto, no perderemos la respuesta si actuamos así: para cada celda j de la fila i (la fila de abajo de una potencial submatriz de ceros) tendremos d[i][j] como la fila de arriba de la submatriz de ceros actual. Ahora resta determinar los bordes izquierdo y derecho óptimos de la submatriz de ceros, es decir, empujar al máximo esta submatriz a la izquierda y a la derecha de la columna j.

¿Qué significa empujar al máximo a la izquierda? Significa encontrar un índice k1 para el cual d[i][k1] > d[i][j], y al mismo tiempo k1 es el más cercano a la izquierda del índice j. Está claro que entonces k1 + 1 da el número de la columna izquierda de la submatriz de ceros requerida. Si no hay tal índice, ponemos k1 = -1 (esto significa que pudimos extender la submatriz de ceros actual a la izquierda hasta el borde de la matriz a).

Simétricamente, se puede definir un índice k2 para el borde derecho: es el índice más cercano a la derecha de j tal que d[i][k2] > d[i][j] (o m, si no hay tal índice).

Así, los índices k1 y k2, si aprendemos a buscarlos de forma efectiva, nos darán toda la información necesaria sobre la submatriz de ceros actual. En particular, su área será igual a (i - d[i][j]) * (k2 - k1 - 1).

¿Cómo buscar estos índices k1 y k2 de forma efectiva con i y j fijos? Podemos hacerlo en $O(1)$ en promedio.

Para lograr esa complejidad, se puede usar la pila de la siguiente manera. Primero aprendamos a buscar un índice k1, y guardemos su valor para cada índice j dentro de la fila actual i en la matriz d1[i][j]. Para esto, recorremos todas las columnas j de izquierda a derecha, y guardamos en la pila solo aquellas columnas que tienen d[][] estrictamente mayor que d[i][j]. Está claro que al pasar de una columna j a la siguiente hay que actualizar el contenido de la pila. Cuando hay un elemento inadecuado en el tope de la pila (es decir, d[][] <= d[i][j]) lo sacamos. Es fácil entender que alcanza con sacar de la pila solo desde su tope, y de ningún otro lugar (porque la pila contendrá una secuencia creciente de d de columnas).

El valor d1[i][j] para cada j será igual al valor que en ese momento está en el tope de la pila.

La dinámica d2[i][j] para encontrar los índices k2 se considera de forma similar, solo que hay que ver las columnas de derecha a izquierda.

Está claro que como hay exactamente m piezas agregadas a la pila en cada línea, no podría haber más borrados tampoco: la suma de complejidades será lineal, así que la complejidad final del algoritmo es $O(nm)$.

También hay que notar que este algoritmo consume $O(m)$ de memoria (sin contar los datos de entrada: la matriz a[][]).

Implementación

int zero_matrix(vector<vector<int>> a) {
    int n = a.size();
    int m = a[0].size();
 
    int ans = 0;
    vector<int> d(m, -1), d1(m), d2(m);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 1)
                d[j] = i;
        }
 
        for (int j = 0; j < m; ++j) {
            while (!st.empty() && d[st.top()] <= d[j])
                st.pop();
            d1[j] = st.empty() ? -1 : st.top();
            st.push(j);
        }
        while (!st.empty())
            st.pop();
 
        for (int j = m - 1; j >= 0; --j) {
            while (!st.empty() && d[st.top()] <= d[j])
                st.pop();
            d2[j] = st.empty() ? m : st.top();
            st.push(j);
        }
        while (!st.empty())
            st.pop();
 
        for (int j = 0; j < m; ++j)
            ans = max(ans, (i - d[j]) * (d2[j] - d1[j] - 1));
    }
    return ans;
}