Acheter et vendre des actions
Étant donné
n entiers représentant les prix de l’action de votre entreprise préférée, vous souhaitez déterminer le meilleur moment pour acheter et vendre cette action. Vous ne voulez l’acheter qu’une seule fois et la vendre également une seule fois. L’objectif est donc de maximiser votre profit (acheter à bas prix et vendre à un prix plus élevé).Il s’agit de trouver le profit maximal que vous pouvez réaliser. Si aucune configuration ne permet de réaliser un profit, vous devez afficher 0 (ce qui signifie que vous ne procéderez à aucune opération d’achat ou de vente).
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ ).La ligne suivante comporte
n entiers séparés par des espaces : , qui représentent les prix de l’action (0 ≤ ≤ 1000).Sortie
Le programme doit afficher le profit maximal que vous pouvez réaliser en achetant et en vendant votre action préférée.
Exemples
Input | Output |
5
4 2 6 8 1 | 6 |
4
8 6 4 3 | 0 |
Explication
- On achète lorsque le prix de l’action est de 2 et on la revend lorsqu’il est de 8.
- Il n’est pas possible de réaliser un profit dans le second cas, car le prix de l’action ne cesse de baisser.
Hint
À chaque instant, vous pouvez conserver un état correspondant à la meilleure solution trouvée jusqu’à présent, et une autre valeur correspondant au prix le plus bas rencontré.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB