> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/1-200/123.-mai-mai-gu-piao-de-zui-jia-shi-ji-iii.md).

# 123. 买卖股票的最佳时机 III

<https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/>

## 解法一：dp

`dp1[i] = max(dp[i-1], prices[i] - minval)` 从前往后遍历，表示第1天买入，第i天之前卖出（包括第i天）的最大利润

`dp2[i] = max(dp[i+1], maxval - prices[i])` 从后往前遍历，表示第i天之后（包括第i天）买入，第n天卖出的最大利润；

`res = max(dp1 + dp2)`，因为`(dp1 + dp2)[i]` 正好表示从第1天到第n天经过**最多两次**交易的最大利润，我们的目标是找到令总利润最大的i。注意虽然不能同时参与多笔交易，但是卖出和买入可以在同一天进行（先卖后买）

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)       
        if n < 2:
            return 0
        dp1 = [0 for _ in range(n)]
        dp2 = [0 for _ in range(n)]
        min_val, max_val = prices[0], prices[n-1]
        #前向
        for i in range(1, n):
            dp1[i] = max(dp1[i-1], prices[i]-min_val)
            min_val = min(min_val, prices[i])
        #后向
        for i in range(n-2, -1, -1):
            dp2[i] = max(dp2[i+1], max_val-prices[i])
            max_val = max(max_val, prices[i])
        #合并输出
        return max([dp1[i]+dp2[i] for i in range(n)])
```

## 解法二：状态机dp

相当于状态机模型中k=2，直接套用188买卖股票的最佳时机 IV的解法，令k=2即可

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        k=2  #令k=2即可套用模板
        if  n == 0:
            return 0
        dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n+1)]

        for i in range(n + 1):
            for j in range(k + 1):
                if i  == 0:
                    dp[i][j][0] = 0
                    dp[i][j][1] = -sys.maxsize
                    continue
                if j  == 0:
                    dp[i][j][0] = 0
                    dp[i][j][1] = -sys.maxsize
                    continue
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i-1])
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i-1])
        return dp[n][k][0]
```