Die Kühe haben ein neues Geschäft eröffnet, und Farmer John möchte sehen, wie gut es läuft. Das Geschäft besteht seit $N$ ($1 \leq N \leq 100{,}000$) Tagen, und jeden Tag $i$ haben die Kühe ihren Nettogewinn $P_i$ ($-1{,}000 \leq P_i \leq 1{,}000$) aufgezeichnet.
Farmer John möchte den größten Gesamtgewinn finden, den die Kühe in irgendeinem zusammenhängenden Zeitraum erzielt haben. (Beachte, dass ein zusammenhängender Zeitraum zwischen einem Tag und $N$ Tagen lang sein kann.) Hilf ihm, indem du ein Programm zur Berechnung der größten Summe aufeinanderfolgender Gewinne schreibst.
Eingabe
Lies die Eingabe von der Standardeingabe.
- Zeile 1: eine einzelne ganze Zahl $N$.
- Zeilen $2..N+1$: Zeile $i+1$ enthält eine einzelne ganze Zahl $P_i$.
Ausgabe
Schreibe die Ausgabe auf die Standardausgabe.
- Zeile 1: eine einzelne ganze Zahl, die die maximale Gewinnsumme für irgendeinen zusammenhängenden Zeitraum angibt.
Beispiele
Eingabe 1
7 -3 4 9 -2 -5 8 -3
Ausgabe 1
14
Hinweis
Die maximale Summe ergibt sich aus den Zahlen von der zweiten bis zur sechsten (4, 9, -2, -5, 8) und beträgt 14.
Autor der Aufgabe: Neal Wu, 2007