Best Time to Buy and Sell Stock II

Средняя№122каждый подъём

Даны цены акции по дням. Покупать и продавать можно сколько угодно раз, но держать не больше одной акции сразу; продать и снова купить в тот же день можно. Найдите наибольшую общую прибыль. Наш пример: [5, 2, 4, 7, 6, 3, 8] — ответ 10: купить за 2 и продать за 7, потом купить за 3 и продать за 8.

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

Пример: [5, 2, 4, 7, 6, 3, 8], столбик на каждый день. Каждый подъём от дня к следующему добавляется в profit; его часть столбика отмечена.

50214273643586profit0
день ещё впередидень i − 1день iподъём, взятый в прибыльпройден

Пока ничего не заработали: profit = 0

01/23
сначала · назад · пуск · шаг
Скорость
1function maxProfit(prices):
2 profit = 0
3 for i from 1 to len(prices) - 1:
4 rise = prices[i] - prices[i - 1]
5 if rise > 0:
6 profit = profit + rise
7 return profit
состояние
profit
0
i
–
rise
–
историянажмите шаг, чтобы вернуться

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

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

  1. Сделка со дня a до дня b приносит prices[b] − prices[a], а это сумма изменений цены по дням между ними. Поэтому одна длинная сделка на подъёме приносит ровно сумму его шагов вверх.
  2. Сделка поверх падения платит за это падение. Выбросить все отрицательные изменения и оставить все положительные — наибольшая сумма, какую они могут дать.
  3. Каждый подъём — сделка на один день, и такие сделки не пересекаются, поэтому эту сумму правда можно заработать, держа одну акцию за раз.

Сложность

Время O(n): один проход по дням. Память O(1): только profit и текущий rise.

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

Решить на LeetCode ↗

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