L'escalade de l'Yggdrasil – Qualification 2024

Niveau 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$

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4
3 2 -5 4
Exemple de sortie
3
Commentaire

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.

Exemple d'entrée
7
2 9 18 12 9 19 1
Exemple de sortie
19
Commentaire

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.

Exemple d'entrée
6
1 6 -7 9 10 -15
Exemple de sortie
10
Commentaire

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.