PrepBro
← Назад к вопросам

Максимальная прибыль от акций

1.0 Junior🔥 171 комментариев
#Python Core

Условие

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

Покупать нужно до продажи.

Пример

max_profit([7, 1, 5, 3, 6, 4]) → 5 Объяснение: купить в день 2 (цена 1), продать в день 5 (цена 6)

max_profit([7, 6, 4, 3, 1]) → 0 Объяснение: цена только падает, нет прибыли

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Максимальная прибыль от акций

Это классическая задача на алгоритмический анализ потоков данных. Нужно найти пару (день покупки, день продажи) такую, что цена падает и прибыль максимальна. Ключевое ограничение: продажа только после покупки.

Подход: Один проход с отслеживанием минимума

В один проход через массив отслеживаем:

  1. Минимальная цена видена до текущего дня
  2. Максимальная прибыль если продать сегодня
def max_profit(prices):
    if not prices or len(prices) < 2:
        return 0
    
    min_price = prices[0]
    max_profit = 0
    
    for price in prices[1:]:
        potential_profit = price - min_price
        max_profit = max(max_profit, potential_profit)
        min_price = min(min_price, price)
    
    return max_profit

print(max_profit([7, 1, 5, 3, 6, 4]))  # 5
print(max_profit([7, 6, 4, 3, 1]))      # 0

Пошаговое выполнение

Массив: [7, 1, 5, 3, 6, 4]

Шаг 1: price=7 (начало)
  min_price = 7, max_profit = 0

Шаг 2: price=1
  profit = 1 - 7 = -6
  max_profit = max(0, -6) = 0
  min_price = min(7, 1) = 1

Шаг 3: price=5
  profit = 5 - 1 = 4
  max_profit = max(0, 4) = 4
  min_price = 1

Шаг 4: price=3
  profit = 3 - 1 = 2
  max_profit = 4
  min_price = 1

Шаг 5: price=6
  profit = 6 - 1 = 5 ← Максимум!
  max_profit = 5
  min_price = 1

Шаг 6: price=4
  profit = 4 - 1 = 3
  max_profit = 5

С отслеживанием дней

def max_profit_with_days(prices):
    if not prices or len(prices) < 2:
        return 0, -1, -1
    
    min_price = prices[0]
    min_day = 0
    max_profit = 0
    buy_day = 0
    sell_day = 0
    
    for day, price in enumerate(prices[1:], 1):
        profit = price - min_price
        
        if profit > max_profit:
            max_profit = profit
            buy_day = min_day
            sell_day = day
        
        if price < min_price:
            min_price = price
            min_day = day
    
    return max_profit, buy_day, sell_day

Наивный подход (неоптимально)

def max_profit_brute_force(prices):
    # O(n^2) - проверяем все пары
    max_profit = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            profit = prices[j] - prices[i]
            max_profit = max(max_profit, profit)
    return max_profit

Полная реализация с тестами

def max_profit(prices):
    if not prices or len(prices) < 2:
        return 0
    
    min_price = prices[0]
    max_profit_val = 0
    
    for price in prices[1:]:
        potential_profit = price - min_price
        max_profit_val = max(max_profit_val, potential_profit)
        min_price = min(min_price, price)
    
    return max_profit_val

test_cases = [
    ([7, 1, 5, 3, 6, 4], 5),
    ([7, 6, 4, 3, 1], 0),
    ([2, 4, 1], 2),
    ([1], 0),
    ([], 0),
    ([5, 5, 5, 5], 0),
    ([1, 2, 3, 4, 5], 4),
]

for prices, expected in test_cases:
    result = max_profit(prices)
    status = "OK" if result == expected else "FAIL"
    print(f"{status} max_profit({prices}) = {result}")

Вариация: Несколько сделок

def max_profit_multiple(prices):
    max_profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            max_profit += prices[i] - prices[i - 1]
    return max_profit

print(max_profit_multiple([7, 1, 5, 3, 6, 4]))  # 7

Анализ сложности

Оптимальное решение:

  • Время: O(n) - один проход
  • Память: O(1) - только переменные

Наивное решение:

  • Время: O(n^2) - все пары
  • Память: O(1)

Почему работает

Максимальная прибыль = max(цена[j] - цена[i]) где i < j

Это равно max(цена[j] - min(цена[0..j-1]))

Поэтому отслеживаем только минимум слева и текущую цену.

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

Максимальная прибыль от акций | PrepBro