Jouer à un jeu de suppression de nombres
Jouons à un jeu. Vous disposez de
n entiers positifs (où n est pair). À chaque étape, vous avez le droit de retirer un nombre soit au début, soit à la fin de la séquence, et de le garder pour vous. Moi (l’ordinateur), je retirerai le plus grand entre le premier et le dernier élément de la séquence. S’ils sont égaux, je prendrai le premier. Nous continuerons à nous relayer de cette façon jusqu’à ce que la liste soit vide.Si vous commencez la partie, quelle est la somme maximale de nombres que vous pouvez obtenir ?
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 1000).La ligne suivante contient
n entiers séparés par des espaces (1 ≤ ≤ ).Sortie
Le programme doit afficher la somme maximale que vous pouvez accumuler.
Exemples
Entrée | Sortie |
4
3 2 10 4 | 13 |
Explication
- Vous prenez le premier 3 →
2 10 4
- L’ordinateur prend le 4 →
2 10
- Vous prenez le 10 →
2
- L’ordinateur prend le 2 ⇒ Vous avez collecté 3 + 10 = 13
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB