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。注意虽然不能同时参与多笔交易，但是卖出和买入可以在同一天进行（先卖后买）

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即可

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]