La Conquête de l'Est – Épreuve régionale 2012

Énoncé¶

Joseph Marchand est un trader. Il achète des biens pour les revendre plus cher. Aidez-le dans sa tâche pour maximiser ses profits.

Joseph arrive à prédire le prix de l'acier sur plusieurs jours. Il peut acheter 1 unité d'acier un jour et le revendre plus tard.

Entrée¶

L'entrée comprendra :

• Le nombre de jour N où Joseph peut prédire le prix de l'acier.
• Sur la seconde ligne, le prix P_i d'une unité d'acier au i-ème jour.

Sortie¶

Le gain maximal que Joseph peut faire en achetant puis vendant une seule unité d'acier durant la période proposée en entrée.

Contraintes¶

• 1 <= N <= 100 000
• 1 <= P_i <= 10 000