Лучшее время для покупки и продажи акций

Сегодня предлагаю вам рассмотреть не очень сложную задачу. Мы будем пытаться обмануть фондовый рынок и заработать очень много денег.

Сложность: 🟠 Cредняя

ℹ️ Описание

Вам дан целочисленный массив цен prices, где prices[i] — цена акции на i-й день.

Каждый день вы можете принять решение о покупке и/или продаже акции. Вы можете одновременно владеть только одной акцией.

Найдите и верните максимальную прибыль, которую вы можете получить.

⚠️ Ограничения

🔹В массиве может быть от 1 до 3 * 10^4 элементов
🔹В качестве значений могут быть числа в диапазоне от 0 до 10 ^ 4


1️⃣ Пример

Входящие данные: [7,1,5,3,6,4]
Ответ: 7

Покупайте в день 2 (цена = 1) и продавайте в день 3 (цена = 5), прибыль = 5-1 = 4. Затем купите в день 4 (цена = 3) и продайте в день 5 (цена = 6), прибыль = 6-3 = 3.

Общая прибыль равна 4 + 3 = 7.

2️⃣ Пример

Входящие данные: [1,2,3,4,5]
Ответ: 4

Покупайте в день 1 (цена = 1) и продавайте в день 5 (цена = 5)

Прибыль = 5-1 = 4.

3️⃣ Пример

Входящие данные: [7,6,4,3,1]
Ответ: 0

Невозможно получить положительную прибыль, поэтому мы никогда не покупаем акции.

Прибыль = 0.


✅ Решение

Эту задачу можно решить как минимум двумя способами, поэтому давайте рассмотрим каждый из них отдельно.

#arrays #medium