Submatriz com a soma máxima
Dada uma matriz de inteiros de dimensão , pretende-se calcular a submatriz que apresente a maior soma.
Entrada
A primeira linha da entrada contém dois inteiros — o número de linhas da matriz r
e o número de colunas c
(1 ≤ r, c ≤ 50).
As próximas r
linhas contêm c
inteiros separados por espaço, que representam os elementos da matriz .
Saída
O programa deve imprimir um único inteiro: a maior soma de uma submatriz.
Exemplos
Entrada | Saída |
---|---|
3 5 | 104 |
Explicação
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