Maximale Teilarraysumme
Gegeben ist ein Array mit
n ganzen Zahlen. Finde ein zusammenhängendes Teilarray, dessen Summe maximal ist.Eingabe
Die erste Zeile der Eingabe enthält eine ganze Zahl
n – die Anzahl der Elemente im Array (1 ≤ n ≤ ).Die nächste Zeile enthält
n durch ein Leerzeichen getrennte ganze Zahlen, die die Elemente des Arrays darstellen .Ausgabe
Das Programm soll eine einzige ganze Zahl ausgeben – die höchstmögliche Summe eines Teilarrays im gegebenen Array.
Beispiele
Eingabe | Ausgabe |
9
-2 1 -3 4 -1 3 1 -4 -2 | 7 |
10
1 -2 3 4 -3 1 7 -10 -20 4 | 12 |
Erklärung
- -2 1 -3
4 -1 3 1-4 -2 → Die Summe des hervorgehobenen Teilarrays ist (4 - 1 + 3 + 1) = 7
- 1 -2
3 4 -3 1 7-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
Kann man das noch besser machen 😎?
Es ist möglich, dieses Problem ohne zusätzliche Arrays zu lösen. Schaffst du das?
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB