Сложность: hard
Вам дан массив цен, где prices[i] — это цена данной акции в i-й день.
Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить не более двух транзакций.
Пример:
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1
👨💻 Алгоритм:
1️⃣Наивная реализация этой идеи заключалась бы в разделении последовательностей на две части и последующем перечислении каждой из подпоследовательностей, хотя это определенно не самое оптимизированное решение. Для последовательности длиной N у нас было бы N возможных разделений (включая отсутствие разделения), каждый элемент был бы посещен один раз в каждом разделении. В результате общая временная сложность этой наивной реализации составила бы O(N²).
2️⃣Мы могли бы сделать лучше, чем наивная реализация O(N²). Что касается алгоритмов разделяй и властвуй, одна из общих техник, которую мы можем применить для оптимизации временной сложности, называется динамическим программированием (DP), где мы меняем менее повторяющиеся вычисления на некоторое дополнительное пространство. В алгоритмах динамического программирования обычно мы создаем массив одного или двух измерений для сохранения промежуточных оптимальных результатов. В данной задаче мы бы использовали два массива, один массив сохранял бы результаты последовательности слева направо, а другой массив сохранял бы результаты последовательности справа налево. Для удобства мы могли бы назвать это двунаправленным динамическим программированием.
3️⃣Сначала мы обозначаем последовательность цен как Prices[i], с индексом начиная от 0 до N-1. Затем мы определяем два массива, а именно left_profits[i] и right_profits[i]. Как следует из названия, каждый элемент в массиве left_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в левой подпоследовательности цен от индекса ноль до i, (т.е. Prices[0], Prices[1], ... Prices[i]). Например, для подпоследовательности [7, 1, 5] соответствующий left_profits[2] будет равен 4, что означает покупку по цене 1 и продажу по цене 5. И каждый элемент в массиве right_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в правой подпоследовательности цен от индекса i до N-1, (т.е. Prices[i], Prices[i+1], ... Prices[N-1]). Например, для правой подпоследовательности [3, 6, 4] соответствующий right_profits[3] будет равен 3, что означает покупку по цене 3 и продажу по цене 6. Теперь, если мы разделим последовательность цен вокруг элемента с индексом i на две подпоследовательности, с левыми подпоследовательностями как Prices[0], Prices[1], ... Prices[i] и правой подпоследовательностью как Prices[i+1], ... Prices[N-1], то общая максимальная прибыль, которую мы получим от этого разделения (обозначенная как max_profits[i]), может быть выражена следующим образом:
max_profits[i] = left_profits[i] + right_profits[i+1]
😎 Решение:
class Solution(object):
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
left_min = prices[0]
right_max = prices[-1]
length = len(prices)
left_profits = [0] * length
# pad the right DP array with an additional zero for convenience.
right_profits = [0] * (length + 1)
# construct the bidirectional DP array
for l in range(1, length):
left_profits[l] = max(left_profits[l - 1], prices[l] - left_min)
left_min = min(left_min, prices[l])
r = length - 1 - l
right_profits[r] = max(right_profits[r + 1], right_max - prices[r])
right_max = max(right_max, prices[r])
max_profit = 0
for i in range(0, length):
max_profit = max(max_profit, left_profits[i] + right_profits[i + 1])
return max_profit
Ставь 👍 и забирай 📚 Базу знаний