Sottomatrice massima
Data una matrice di interi di dimensioni , è richiesto di individuare la sottomatrice con la somma massima.
Ingresso
La prima riga dell’input contiene due interi: il numero di righe della matrice
r e il numero di colonne c (1 ≤ r, c ≤ 50).Le successive
r righe contengono c interi separati da uno spazio, che rappresentano gli elementi della matrice .Uscita
Il programma deve stampare un singolo intero: la somma massima della sottomatrice.
Esempi
Ingresso | Uscita |
3 5
1 2 -3 4 -6
-1 3 -100 4 0
0 1 -2 0 100 | 104 |
Spiegazione
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