[Leetcode 123] Best Time to Buy and Sell Stock III

Question

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

思路 这是一个动态规划问题。首先最开始收入为0； 我们用 firstBuy=INT_MIN, firstSell=0, secondBuy=INT_MIN, secondSell=0; 分别表示第一次买进的 收益（负数）， 第一次买出的 收益， 第二次买进的收益，第二次卖出的 收益。 他们的递推公式如下：

// a表示当天的股票价格 firstBuy=max(firstBuy, -a); firstSell=max(a+firstBuy,firstSell); secondBuy=max(secondBuy,firstSell-a); secondSell=max(secondBuy+a,secondSell);

例如： prices={2,1,2,0,1}

股票价格firstBuyfirstSellsecondBuysecondSell2-20-201-10-102-11-110011110112

最大收益为2.

代码如下： class Solution { public: int maxProfit(vector<int>& prices) { int firstBuy=INT_MIN,secondBuy=INT_MIN,firstSell=0,secondSell=0; for(auto &a：prices){ firstBuy=max(firstBuy, -a); firstSell=max(a+firstBuy,firstSell); secondBuy=max(secondBuy,firstSell-a); secondSell=max(secondBuy+a,secondSell); } return max(secondSell,firstSell); } };