Submatriz máxima
Dada una matriz de enteros de dimensiones , se te solicita calcular la submatriz que tenga la suma más grande.
Entrada
La primera línea de la entrada contiene dos números enteros: la cantidad de filas
r y la cantidad de columnas c (1 ≤ r, c ≤ 50).A continuación, se proporcionan
r líneas, cada una con c números enteros separados por un espacio, que representan los elementos de la matriz .Salida
El programa debe imprimir un único número entero que represente la suma más alta de la submatriz.
Ejemplos
Entrada | Salida |
3 5
1 2 -3 4 -6
-1 3 -100 4 0
0 1 -2 0 100 | 104 |
Explicación
1 | 2 | -3 | 4 | -6 |
-1 | 3 | -100 | 4 | 0 |
0 | 1 | -2 | 0 | 100 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB