题目链接：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
