¿Cuál es el enfoque algorítmico para encontrar el tamaño de la submatriz rectangular máxima que tiene todos los 1 de una matriz que contiene 0 y 1?

Procese las líneas en orden consecutivo, por ejemplo, de 1 a N. Mantenga un recuento de la altura de cada columna (número de unidades). Para cada línea,

• Procese las celdas en la línea actual; si tiene el valor 0, la altura se establece en 0; de lo contrario, increméntela.
• Encuentra el rectángulo más grande cuya base es la línea actual. Esto es lo mismo que el rectángulo más grande en un problema de histograma, que se puede resolver en tiempo lineal. ¿Cuál es el enfoque algorítmico para encontrar el área rectangular máxima en un histograma?

Para cada línea, nos tomamos el tiempo [matemático] O (M) [/ matemático] para actualizar las alturas y [matemático] O (M) [/ matemático] para encontrar el rectángulo más grande en un histograma. Por lo tanto, este enfoque es [matemático] O (N * M) [/ matemático].

Aquí hay un artículo realmente bueno de GeeksForGeeks para aprender más sobre problemas de programación dinámica similares e incluso ofrece una declaración generalizada para su pregunta (la suma máxima de cualquier rectángulo con cualquier número, no solo 0 y 1). El enlace es el siguiente: Programación dinámica | Conjunto 27 (rectángulo de suma máxima en una matriz 2D) – GeeksforGeeks

Esta es la mejor solución –

Submatriz cuadrada de tamaño máximo con todos los 1s – GeeksforGeeks

También lea los comentarios, sus dudas, si las hay, probablemente serán aclaradas.