L'escalade de l'Yggdrasil – Qualification 2024

Level 1 ⋅ Validation weight: 100%

Énoncé

Jøsëf Marchand, désireux d'aider les dieux, croise au pied de l'Yggdrasil, Höder. Le dieu étant aveugle, celui-ci lui demande de l'aide pour rejoindre le haut de l'arbre afin de retrouver sa famille et de participer à la photo familiale.

Höder se déplace en effectuant des sauts de branche en branche.

Jøsëf connait les $N$ différences de hauteur entre les branches consécutives de l'Yggdrasil.

Aidez Jøsëf à calculer le plus grand saut qu'Höder devra faire entre la première branche et la branche la plus haute de l'arbre.

On ne considère dans ce calcul que les sauts qui font prendre de la hauteur, c'est à dire ceux qui décrivent une différence de hauteur positive. Si la première branche, sur laquelle Höder se situe, est déjà la branche la plus haute, alors affichez 0.

Si plusieurs branches se situent à la hauteur maximale, alors la photo de famille se trouvera sur la première d'entre elles.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de branches de l'arbre moins 1.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : differences, la liste des différences en hauteur des branches consécutives.

Sortie

Afficher le plus grand saut que devra effectuer Höder pour atteindre la branche la plus haute de l'Yggdrasil.

Contraintes

  • $1 \le N \le 20$

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
4
3 2 -5 4
Sample output
3
Note

Supposons que la première branche, où se situe Höder initialement, est à la hauteur 1. Alors les branches se situent aux hauteurs : 1, 4, 6, 1, 5. La branche la plus haute est la troisième à une hauteur de 6. Höder doit donc faire un saut de 3 puis un saut de 2 pour l'atteindre. Le saut le plus grand qu'il devra effectuer est ainsi le plus grand nombre entre 2 et 3, c'est-à-dire 3. La valeur à afficher est donc 3.

Sample input
7
2 9 18 12 9 19 1
Sample output
19
Note

Nous avons ici uniquement des valeurs positives, la branche la plus haute est la dernière. De ce fait, le saut le plus grand que Höder devra effectuer sera le nombre le plus grand dans la liste, soit 19.

Sample input
6
1 6 -7 9 10 -15
Sample output
10
Note

Supposons encore que la première branche est à la hauteur 1. La hauteur des branches de ce test correspond alors à cette liste : 1, 2, 8, 1, 10, 20, 5. Nous pouvons remarquer que la branche la plus haute est l'avant-dernière. De ce fait, nous cherchons le saut le plus grand avant la branche de hauteur 20. Il faut donc afficher 10.

Submit your solution

You have to register or log in to be able to submit your solution.