Leetcode 123 Best Time to Buy and Sell Stock III

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).

承接121和122题，最多可以交易两次。

最直接的想法是将121的做法来两次，正一遍，反一遍，然后枚举中间点，求两边和的最大值。

后来在discuss中看到了更优美的解法。

四个变量，分别表示第一次买完，第一次卖完，第二次买完，第二次卖完后手上的钱。

那么转移就很好写了，每次操作完都要保证手上的钱最多，

b1为之前的值和买当前股票的最大值。

s1为s1和卖掉股票+b1的最大值。

b2、s2以此类推。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int b1=INT_MIN,b2=INT_MIN;
        int s1=0,s2=0;
        for(int i=0;i<prices.size();i++)
        {
            b1=max(b1,-prices[i]);
            s1=max(s1,b1+prices[i]);
            b2=max(b2,s1-prices[i]);
            s2=max(s2,b2+prices[i]);
        }
        return s2;
    }
};