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