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