Maximale Teilmatrix
Gegeben ist eine -Matrix mit ganzen Zahlen. Gesucht wird die Teilmatrix, deren Summe am größten ist.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen – die Anzahl der Zeilen r und die Anzahl der Spalten c (1 ≤ r, c ≤ 50).
Die folgenden r Zeilen enthalten jeweils c ganzzahlige Werte, getrennt durch ein Leerzeichen, die die Elemente der Matrix darstellen .
Ausgabe
Es soll genau eine ganze Zahl ausgegeben werden – die größtmögliche Summe einer Teilmatrix.
Beispiele
Eingabe | Ausgabe |
|---|---|
3 5 | 104 |
Erläuterung
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