123. Best Time to Buy and Sell S

原题连接：Best Time to Buy and Sell Stock III

题目要求：
Say you have an array for which the i^th 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).

这道题不同于Best Time to Buy and Sell Stock I和Best Time to Buy and Sell Stock II。这里要求最多交易两次，难度大大提升，参见网友Code Ganker的博客，可以先解释最多可以进行k次交易的算法，然后最多进行两次只需要把k取成2即可，使用局部最优和全局最优方法。

• 全局最优：global[i][j]表示第i天最多进行j次交易的最好利润
• 局部最优：local[i][j]表示第i天最多进行j次交易的并且在最后一次交易在当天的卖出的最好利润

下面看一下递推式，

global[i][j] = max(local[i][j],global[i-1][j])
比较当前局部最好的，以及前一天全局最好的那个

local[i][j] = max(global[i-1][j-1],local[i-1][j])+dif
详细解释参见 grandyang的博客

运用此方法代码如下

 int maxProfit(vector<int>& prices) {
        if(prices.empty())return 0;
        int row = prices.size();
        vector<vector<int>> global(row);
        vector<vector<int>> local(row);
        for(int i=0;i<row;i++){
            global[i].assign(3,0);
            local[i].assign(3,0);
        }
        for(int i=1;i<row;i++){
            int dif = prices[i]-prices[i-1];
            for(int j=1;j<=2;j++){
                local[i][j] = max(global[i-1][j-1],local[i-1][j])+dif;
                global[i][j] = max(local[i][j],global[i-1][j]);
            }
        }
        return global[row-1][2];
    }

此方法耗费空间比较大，在LeetCode提交的答案中找到一种好方法，先贴代码如下

int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        vector<vector<int>> dp(3, vector<int>(prices.size(), 0));
        for (int num_trans = 1; num_trans <= 2; ++num_trans) {
            int min_dept = -prices[0];
            for (int day = 1; day < prices.size(); ++day) {
                dp[num_trans][day] = max(dp[num_trans][day - 1], prices[day] + min_dept);
                min_dept = max(min_dept, dp[num_trans - 1][day - 1] - prices[day]);
            }
        }
        return dp[2][prices.size() - 1];
    }

dp[num_trans][day]是整个交易的状态空间，它的值代表最大利润，横坐标表示交易次数，纵坐标表示交易天数，由于题目要求交易次数不超过两次，所以num_trans≤2。以输入prices={3,3,5,0,0,3,1,4}为例，二维数组dp状态更新如下表格：

其中，表格里的值代表最大利润指，如6代表第7天最多交易不超过2次的最大利润。