Best Time to Buy and Sell Stock

+10

Дан список prices, где prices[i] — цена одной акции в день i. Ты можешь купить одну акцию в какой-то день и продать её в более поздний день. Верни максимальную прибыль, которую можно получить, или 0, если любая возможная сделка приносит убыток.

Функция

maxProfit(prices: integer-array) → integer

pricesinteger-array: цена акции в каждый день, по порядку
Возвращаетinteger: наибольшая прибыль от одной покупки и последующей продажи или 0

Ограничения

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴
Вы совершаете не более одной сделки и продаёте в день, который наступает позже дня покупки.

Примеры

Ввод: prices = [7, 2, 5, 9, 1, 4]
Вывод: 7
Пояснение: Купи в день 1 по цене 2 и продай в день 3 по цене 9, получив прибыль 7. Самая низкая цена — 1 в день 4 — встречается после цены 9, поэтому лучшая продажа после неё принесёт только 3.

Дополнительный вопрос

Что, если можно совершать сколько угодно сделок, держа при этом не более одной акции одновременно?

Решение

Сначала нужно купить, а потом продать, поэтому ответ — не самая высокая цена минус самая низкая. Для каждого дня, когда можно продать, лучший день для покупки — самый дешёвый из предыдущих. Если отслеживать эту минимальную цену по мере продвижения, задача решается за один проход.

Попробуйте каждую пару покупки и продажи

Верно, но не успевает на самых больших тестах

Идея

Каждая сделка — это день покупки и более поздний день продажи, поэтому проверь каждую пару и сохрани наибольшую разницу. Начальное значение лучшей прибыли 0 учитывает возможность не совершать сделку. Проверяется каждая допустимая сделка, поэтому ответ верен.

В списке из n цен примерно n²/2 пар: 100,000 дней означают примерно 5 миллиардов вычитаний.

Алгоритм

Установи best равным 0.
Перебери каждый день покупки buy.
Для каждого из них перебери каждый день продажи sell после него.
Вычти prices[buy] из prices[sell] и сохрани результат в best, если он больше.
Верни best.

def maxProfit(prices):
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

Один проход с минимальной ценой на данный момент

Идея

Зафиксируй день продажи i. Лучше всего было купить в самый дешёвый день до i включительно, поэтому лучшая сделка, завершающаяся в день i, приносит prices[i] минус самая низкая цена на данный момент. Для каждого дня продажи подбирается лучший день покупки, поэтому ответ — наибольшая из этих прибылей. В день, когда устанавливается новый минимум, прибыль равна 0 — так же, как если бы ты не совершал сделку.

Алгоритм проходит по каждой цене один раз и хранит два числа: lowest и best. Время — O(n), память — O(1).

Алгоритм

Присвой lowest значение первой цены, а best — значение 0.
Просмотри цены по порядку.
Если текущая цена меньше lowest, присвой ей значение нового lowest.
Вычти lowest из текущей цены и сохрани результат в best, если он больше текущего значения.
Верни best.

def maxProfit(prices):
    lowest = prices[0]
    best = 0
    for price in prices:
        if price < lowest:
            lowest = price
        elif price - lowest > best:
            best = price - lowest
    return best

Ловушки и крайние случаи

Возвращать максимальную цену минус минимальную. Для [7, 2, 5, 9, 1, 4] это даст 8, но 1 идёт после 9. Ответ — 7.
Позволять ответу быть отрицательным. Для [9, 7, 4, 3, 1] наилучшая разница равна -1; задайте best значение 0, а не первую разницу.
Задавать lowest значение 0. Тогда каждая прибыль будет равна самой цене, поэтому для [9, 7, 4, 3, 1] вернётся 9. Задайте ему значение первой цены.

Частые вопросы3

Какова временная сложность задачи «Лучшее время для покупки и продажи акций»?

Решение за один проход работает за время O(n) для n дней, поскольку считывает каждую цену один раз, и использует O(1) дополнительной памяти: минимальную цену на данный момент и максимальную прибыль. Проверка каждой пары дней занимает время O(n²).

Почему бы не вычесть самую низкую цену из самой высокой?

Самая низкая цена может идти после самой высокой, а покупать нужно до продажи. В [7, 2, 5, 9, 1, 4] число 1 идёт после 9, поэтому при наиболее выгодной допустимой сделке нужно купить по цене 2 и продать по цене 9, получив прибыль 7.

«Лучшее время для покупки и продажи акций» — это задача на динамическое программирование?

Это можно понимать обоими способами. Самая низкая цена на данный момент — это небольшое состояние, которое ты обновляешь каждый день; так выглядит подход динамического программирования. Сопоставление каждой продажи с самым дешёвым из предшествующих дней — это жадный подход. Оба подхода приводят к одному и тому же коду, который выполняется за один проход.

def maxProfit(prices):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

prices = [7, 2, 5, 9, 1, 4]

Ожидаемый вывод