Best Time to Buy and Sell Stock III

Сложная№123состояния

Дана цена одной акции по дням. Можно сделать не больше двух сделок, каждая — покупка и продажа позже; держать можно одну акцию за раз, поэтому вторая покупка идёт после первой продажи (можно в тот же день). Нужно найти наибольшую общую прибыль или 0, если ни одна сделка не выгодна. Наш пример: [2, 6, 3, 9, 4, 5] → 10, из сделок 2 → 6 и 3 → 9.

123 Best Time to Buy and Sell Stock IIIРазбор · 1×

Пример: цены [2, 6, 3, 9, 4, 5], не больше двух сделок. Смотрите на день 2: вторая акция покупается по 3 на прибыль от 2 → 6, и в день 3 эта пара сделок приносит больше, чем одна сделка 2 → 9.

деньстартцена021623394455buy1-2sell1buy2sell2
сегодня, этот шаглучшие деньги в этом состоянии после того дняберём отсюдаответ и его сделки

До дня 0 держать первую акцию — значит заплатить 2: buy1 = -2

01/41
сначала · назад · пуск · шаг
Скорость
1function maxProfit(prices):
2 buy1 = -prices[0] // holding the 1st share
3 sell1 = 0 // the 1st trade is closed
4 buy2 = -prices[0] // holding the 2nd share
5 sell2 = 0 // the 2nd trade is closed
6 for d from 0 to len(prices) - 1:
7 p = prices[d]
8 buy1 = max(buy1, -p)
9 sell1 = max(sell1, buy1 + p)
10 buy2 = max(buy2, sell1 - p)
11 sell2 = max(sell2, buy2 + p)
12 return sell2
состояние
d
–
p
–
buy1
-2
sell1
–
buy2
–
sell2
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

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

  1. Четыре состояния описывают любой момент: держим первую акцию, первая продана, держим вторую, вторая продана. Каждый день состояние либо остаётся прежним, либо в него приходят из предыдущего по сегодняшней цене, поэтому его число — лучшее среди всех историй, которые в нём кончаются.
  2. buy2 = sell1 − p оплачивает вторую акцию из прибыли первой сделки. Так 2 → 6 и 3 → 9 (10) обгоняют одну сделку 2 → 9 (7): из падения с 6 до 3 мы выходим, а не пересиживаем его.
  3. Состояния обновляются одно за другим в тот же день, так что следующее может прочитать значение, записанное сегодня. Это лишь добавляет покупку и продажу по одной цене, которые дают 0, поэтому лишняя прибыль не появляется.

Сложность

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

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.