Цель — найти максимальную прибыль от одной операции покупки-продажи в массиве цен. Ключевое понимание: нам нужно купить как можно дешевле и продать как можно дороже после покупки.
Мы решаем это за один проход (O(n)), отслеживая два значения одновременно:
minPrice — самая низкая цена, встреченная до сих пор (лучший момент для покупки)profit — максимальная достижимая прибыль до сих порДля каждой цены мы сначала обновляем минимальную цену, затем проверяем, даёт ли продажа по текущей цене бо́льшую прибыль.
function maxProfit(prices) {
let minPrice = prices[0];
let profit = 0;
for (const price of prices) {
minPrice = Math.min(minPrice, price);
profit = Math.max(profit, price - minPrice);
}
return profit;
}
minPrice, гарантируя, что продажа никогда не происходит раньше покупкиprofit остаётся 0, корректно сигнализируя, что прибыльной сделки не существуетO(n) — один проход по массивуO(1) — используются только две переменные вне зависимости от размера входных данныхАлгоритм обновляет minPrice перед расчётом прибыли, чтобы гарантировать, что цена продажи всегда приходится на позицию после цены покупки в массиве.
Новый — ещё не проверен сообществом
Вы