Cambrioler des maisons
Vous prévoyez de cambrioler des maisons dans une rue. Il y a
n maisons et vous connaissez à l’avance la somme d’argent que vous pouvez dérober dans chacune d’elles. Le système d’alarme contactera automatiquement la police si deux maisons voisines sont cambriolées la même nuit.Quel est le montant maximal que vous pourriez obtenir en une seule nuit sans vous faire prendre ?
Entrée
La première ligne de l’entrée contient un seul entier
n (1 ≤ n ≤ ).La ligne suivante contient
n entiers séparés par des espaces (1 ≤ ≤ ), qui indiquent la somme que vous pouvez voler dans chaque maison.Sortie
Le programme doit afficher le montant maximal que vous pouvez obtenir sans vous faire prendre.
Exemples
Entrée | Sortie |
4
1 2 5 1 | 6 |
5
3 17 12 3 7 | 24 |
Explication
- 1 + 5
- 17 + 7 (en sautant quelques maisons au milieu)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB