Ein Spiel, bei dem wir Zahlen entfernen
Lass uns ein Spiel spielen. Du hast
n positive ganze Zahlen (wobei n gerade ist). In jedem Zug darfst du eine Zahl entweder vom Anfang oder vom Ende der Sequenz entfernen und für dich behalten. Ich (der Computer) entferne jeweils die größere der beiden verfügbaren Zahlen vom Anfang oder Ende. Sind diese gleich groß, nehme ich die erste. Wir wechseln uns gegenseitig ab, bis alle Zahlen aus der Liste entfernt wurden.Wenn du den ersten Zug machst, welchen maximalen Betrag kannst du am Ende sammeln?
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 1000).Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ).Ausgabe
Das Programm soll die maximale Summe ausgeben, die du sammeln kannst.
Beispiele
Eingabe | Ausgabe |
4
3 2 10 4 | 13 |
Erklärung
- Du nimmst zuerst die 3 →
2 10 4
- Der Computer nimmt die 4 →
2 10
- Du nimmst die 10 →
2
- Der Computer nimmt die 2 ⇒ Deine gesammelte Summe ist 3 + 10 = 13
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB