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 | 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