Häuser ausrauben
Du planst, Häuser in einer Straße auszurauben. Es gibt
n Häuser, und du weißt, wie viel Geld du aus jedem Haus erbeuten kannst. Das Alarmsystem ruft automatisch die Polizei, wenn in derselben Nacht zwei benachbarte Häuser ausgeraubt werden.Wie hoch ist der maximale Betrag, den du in einer Nacht erbeuten kannst, ohne erwischt zu werden?
Eingabe
Die erste Zeile der Eingabe enthält eine einzige ganze Zahl
n (1 ≤ n ≤ ).Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ), welche den Betrag darstellen, den du aus jedem Haus rauben kannst.Ausgabe
Dein Programm soll den maximal möglichen Betrag ausgeben, den du erbeuten kannst, ohne erwischt zu werden.
Beispiele
Input | Output |
4
1 2 5 1 | 6 |
5
3 17 12 3 7 | 24 |
Erklärung
- 1 + 5
- 17 + 7 (einige Häuser werden dabei übersprungen)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB