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
1 2 -3 4 -6
-1 3 -100 4 0
0 1 -2 0 100 | 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