123. Best Time to Buy and Sell Stock III

题目链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/
题目标签：Array，DP

与 122. Best Time to Buy and Sell Stock II 相比，此题可以最多进行两次交易。所以我们在遍历prices的时候要同时更新buy1，sell1和buy2，sell2。初始化如下：

buy1 = -prices[0]  #为了运算方便，初始化为负数。buy1可以理解为前i天操作序列最后一次操作为买入的最大收益
sell1 = 0  # 前i天操作序列最后一次操作为卖出的最大收益
buy2 = -prices[0]
sell2 = 0

迭代公式如下：

buy2 = max(buy2, sell1 - prices[i]
sell2 = max(sell2, buy2 + prices[i])
buy1 = max(buy1, -prices[i])
sell1 = max(sell1, buy1 + prices[i])

Java代码：

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length==0){
            return 0;
        }
        int buy1 = -prices[0];
        int sell1 = 0;
        int buy2 = -prices[0];
        int sell2 = 0;
        for (int i=1; i<prices.length; i++){
            sell2 = Math.max(sell2, prices[i] + buy2);
            buy2 = Math.max(buy2, sell1-prices[i]);
            sell1 = Math.max(sell1, prices[i] + buy1);
            buy1 = Math.max(buy1, -prices[i]);
        }
        return sell2;
    }
}

Python 代码：

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0
        n = len(prices)
        b1 = -sys.maxint
        s1 = 0
        b2 = -sys.maxint
        s2 = 0
        
        for i in range(n):
            b1 = max(-prices[i], b1)
            s1 = max(prices[i]+b1, s1)
            b2 = max(s1-prices[i], b2)
            s2 = max(prices[i]+b2, s2)
        return s2