# 123. Best Time to Buy and Sell Stock III¶

## Information¶

• Diffculty: Hard

• Created: 2020-03-11 08:33:00

• Last Motified: 2020-03-11 09:02:12

• Tags: Array, Dynamic Programming

## Intuition¶

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).

## Solution¶

```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
```