Цель — найти максимальную прибыль из одной операции купли-продажи, то есть мы покупаем по самой низкой цене перед продажей.
Мы используем жадный подход за O(n) за один проход — не нужно сравнивать каждую пару цен. Мы отслеживаем две переменные:
min_price — самая низкая цена, встреченная до сих пор (лучший момент для покупки)max_profit — максимальная прибыль, достижимая до сих порНа каждом шаге мы проверяем, превышает ли продажа по текущей цене записанную максимальную прибыль, а затем при необходимости обновляем минимальную цену.
def max_profit(prices):
min_price = prices[0]
max_prof = 0
for price in prices[1:]:
max_prof = max(max_prof, price - min_price)
min_price = min(min_price, price)
return max_prof
min_price первой ценой в спискеmax_prof значением 0 (нет сделки — нет прибыли)price - min_pricemax_prof, если эта прибыль большеmin_price, если текущая цена нижеO(n) — один проход по спискуO(1) — хранятся только две переменныеМы всегда обновляем прибыль перед обновлением минимальной цены. Это гарантирует, что мы никогда не продадим раньше, чем купили — минимальная цена, использованная в каждом расчёте, всегда встречалась раньше в массиве.
Алгоритм сохраняет min_price как самую низкую цену, встреченную до этого момента, что гарантирует, что мы никогда не продадим по цене, которая была раньше самой низкой цены покупки, благодаря последовательному характеру однопроходного обхода.
Новый — ещё не проверен сообществом
Вы