Since there could be at most 2 transactions (not k transactions), we could split the prices into 2 parts, left and right.
It's simple to get the maximum transaction for any i with prices[0:i] or prices[i:n] in O(n) time. So we could easily get the maximum 2 transactions with an additional loop. And the overall time complexity is O(n).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
left_profit = [0] * (n + 1)
right_profit = [0] * (n + 1)
min_price = prices[0]
for i, p in enumerate(prices):
if p < min_price:
min_price = p
left_profit[i + 1] = max(left_profit[i], p - min_price)
max_price = prices[-1]
for i in range(n - 1, -1, -1):
p = prices[i]
if p > max_price:
max_price = p
right_profit[i] = max(right_profit[i + 1], max_price - p)
max_profit = 0
for i in range(n):
max_profit = max(max_profit, left_profit[i] + right_profit[i])
return max_profit