Kauf und Verkauf von Aktien
Angenommen, es gibt
n ganzzahlige Werte, die den Aktienkurs deines Lieblingsunternehmens darstellen. Du möchtest den besten Zeitpunkt ermitteln, um diese Aktie zu kaufen und wieder zu verkaufen. Dabei sollst du die Aktie nur einmal kaufen und nur einmal verkaufen. Dein Ziel ist, den Gewinn zu maximieren (also möglichst günstig kaufen und zu einem höheren Preis verkaufen).Bestimme den maximal möglichen Gewinn, den du mit der Aktie deines Lieblingsunternehmens erzielen kannst. Falls es keine Möglichkeit gibt, einen Gewinn zu machen, soll 0 ausgegeben werden (das bedeutet, dass die Aktie weder gekauft noch verkauft wird).
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ).Die nächste Zeile enthält durch Leerzeichen getrennte Werte , die die jeweiligen Aktienpreise repräsentieren (0 ≤ ≤ 1000).
Ausgabe
Das Programm soll den maximal möglichen Gewinn ausgeben, der beim Kauf und Verkauf dieser Aktie erzielt werden kann.
Beispiele
Eingabe | Ausgabe |
5
4 2 6 8 1 | 6 |
4
8 6 4 3 | 0 |
Erklärung
- Wir kaufen, wenn der Aktienkurs bei 2 liegt, und verkaufen, wenn er bei 8 steht.
- Hier ist kein Gewinn möglich, da der Aktienkurs kontinuierlich sinkt.
Hinweis
An jedem Punkt kannst du dir einerseits den aktuell besten möglichen Gewinn merken und andererseits den günstigsten Kurs, der bisher aufgetreten ist.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB