UVa Online Judge – 836 – Largest Submatrix
El link del problema es el siguiente:
836 – Largest Submatrix
El problema es de Programación Dinámica.
Lo que nos piden es encontrar el rectángulo de números ‘1’ mas grande en la matriz.
Esto se reduce a un Max Sum.
La idea es utilizar programación dinámica para generar todos los posibles rectángulos y de lo obtenido, decir el tamaño del rectángulo mas grande.
Los únicos detalle son:
- Los números ‘0’ de la matriz, hay que pasarlos a un numero negativo lo suficiente mente grande. Un valor de -1000 es suficiente
- Hay que dejar un enter entre cada caso de prueba.
El algoritmo de Max Sum que calcula todos los rectángulos es de complejidad O(n^4) que da Accepted en el problema.
Igual existe la solución de Max Sum en un tiempo de complejidad O(n^3).
Jorge Rodriguez Blog 