Сложность: medium
Вам дан массив целых чисел prices, где prices[i] — это цена данной акции в i-й день.
Каждый день вы можете решить купить и/или продать акцию. Вы можете держать в руках только одну акцию за раз. Однако вы можете купить её и сразу же продать в тот же день.
Найдите и верните максимальную прибыль, которую вы можете получить.
Пример:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
👨💻 Алгоритм:
1️⃣Предположим, что дан массив:
\[ 7, 1, 5, 3, 6, 4 \]
Если мы изобразим числа данного массива на графике, мы получим: *приложенное изображение*
2️⃣Анализируя график, мы замечаем, что точки интереса — это последовательные впадины и пики.
Математически говоря:
Общая прибыль = ∑ (высота(пик i) - высота(впадина i))
3️⃣Ключевой момент заключается в том, что мы должны учитывать каждый пик, следующий сразу за впадиной, чтобы максимизировать прибыль. Если мы пропустим один из пиков (пытаясь получить больше прибыли), мы потеряем прибыль по одной из сделок, что приведет к общей меньшей прибыли.
Например, в вышеуказанном случае, если мы пропустим пик i и впадину j, пытаясь получить больше прибыли, рассматривая точки с большей разницей в высотах, чистая прибыль всегда будет меньше, чем та, которая была бы получена при их учете, поскольку C всегда будет меньше, чем A+B.
😎 Решение:
var maxProfit = function (prices) {
let i = 0;
let valley = prices[0];
let peak = prices[0];
let maxprofit = 0;
while (i < prices.length - 1) {
while (i < prices.length - 1 && prices[i] >= prices[i + 1]) i++;
valley = prices[i];
while (i < prices.length - 1 && prices[i] <= prices[i + 1]) i++;
peak = prices[i];
maxprofit += peak - valley;
}
return maxprofit;
};Ставь 👍 и забирай 📚 Базу знаний