Покупка и продажа акций
У вас есть
n целых чисел, которые представляют цены акций вашей любимой компании. Ваша цель — выбрать, когда лучше всего купить акцию и когда лучше всего её продать. Вы хотите купить акцию только один раз и продать её тоже только один раз. Таким образом, вы стремитесь получить максимальную прибыль (купить дёшево и продать дорого).Определите максимально возможную прибыль, которую вы можете получить, покупая и продавая акции вашей любимой компании. Если прибыль получить невозможно, выведите 0 (то есть вы не будете совершать сделку).
Входные данные
В первой строке входных данных содержится одно целое число
n (1 ≤ n ≤ ).Во второй строке указаны разделённые пробелами числа , обозначающие цены акций (0 ≤ ≤ 1000).
Выходные данные
Программа должна вывести максимально возможную прибыль, которую можно получить при покупке и продаже данной акции.
Примеры
Входные данные | Выходные данные |
5
4 2 6 8 1 | 6 |
4
8 6 4 3 | 0 |
Пояснение
- Мы покупаем акцию, когда её цена равна 2, и продаём, когда цена равна 8.
- Получить прибыль невозможно, так как цены акций снижаются на всём протяжении.
Подсказка
В каждый момент времени вы можете хранить текущее «лучшее» решение и отдельно отслеживать минимальную цену, которая встречалась ранее.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB