123. Best Time to Buy and Sell Stock III

problem description

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 (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

algorithm thought

首先知道这里是最多允许买两次，意思是如果一次可以，那就买一个。就像example 2展示的那样，一次交易即可。那么我们还是以第一题（一次交易得到最大值），为基础解此题。

在一次交易的基础上，在第一次交易的结果上，我们减去当前价格，也就是减去第二次购买的成本。每次遍历都计算此值，得到最大值，也就是第二次购买的最便宜的时候。

然后在上面得到第二次最低成本的情况下，得到第二次的最高利润，每遍历到一个数都记录。

最后这里需要仔细想清楚这里的思想以及代码里是如何进行的。不然很难理解，我个人也是第三次做这个题了，也都需要仔细回味

code

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

algorithm analysis

一次遍历解决问题，时间复杂度O(n)