Best Time to Buy and Sell Stock IV

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

Дано число k и цена одной акции по дням. Можно сделать не больше k сделок, каждая — покупка и продажа позже, держать можно одну акцию за раз. Нужно найти наибольшую общую прибыль или 0, если ни одна сделка не выгодна. Наш пример: k = 2, цены [1, 6, 4, 9, 2, 5] → 11, из сделок 1 → 9 и 2 → 5.

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

Пример: k = 2, цены [1, 6, 4, 9, 2, 5]: три подъёма, а сделок можно две. Смотрите на дни 4 и 5: вторая акция меняется на купленную по 2 после 1 → 9, и этот план обгоняет 1 → 6 и 4 → 9.

деньстартцена011624394255sell[0]0buy[1]sell[1]0buy[2]sell[2]0
сегодня, этот шаглучшие деньги в этом состоянии после того дняберём отсюдаответ и его сделки

sell[j]: больше всего денег, когда закончено j сделок. До дня 0 ничего не продано: sell = [0, 0, 0]

01/45
сначала · назад · пуск · шаг
Скорость
1function maxProfit(k, prices):
2 sell = array of k + 1 zeros // j trades done
3 buy = array of k + 1, buy[1..k] = -prices[0]
4 for each p in prices:
5 for j from 1 to k:
6 buy[j] = max(buy[j], sell[j - 1] - p)
7 sell[j] = max(sell[j], buy[j] + p)
8 return sell[k]
состояние
buy
–
sell
[0, 0, 0]
p
–
j
–
историянажмите шаг, чтобы вернуться

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

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

  1. buy[j] и sell[j] — состояния j-й сделки: держим её акцию и закончили с ней. j-я покупка начинается от sell[j − 1], денег после j − 1 сделок, поэтому сделки идут одна за другой и не пересекаются.
  2. k ограничивает число сделок, потому что sell[k + 1] нет. При трёх подъёмах и k = 2 таблица выбирает: пересидеть падение 6 → 4 стоит 2, бросить самый маленький подъём 2 → 5 стоило бы 3, поэтому 1 → 9 и 2 → 5 (11) лучше, чем 1 → 6 и 4 → 9 (10).
  3. Каждый день состояние сохраняет вчерашнее значение или приходит из предыдущего по сегодняшней цене, поэтому sell[k] — лучшее среди всех способов расставить не больше k сделок.

Сложность

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

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

Решить на LeetCode ↗

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