[leetcode] 123. Best Time to Buy and Sell Stock III

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.      

分析一

• 這裡我們先解釋最多可以進行k次交易的算法，然後最多進行兩次我們隻需要把k取成2即可。我們還是使用“局部最優和全局最優解法”。我們維護兩種量，一個是目前到達第i天可以最多進行j次交易，最好的利潤是多少（global[i][j]），另一個是目前到達第i天，最多可進行j次交易，并且最後一次交易在當天賣出的最好的利潤是多少（local[i][j]）。下面我們來看遞推式，全局的比較簡單，

  global[i][j]=max(local[i][j],global[i-1][j])，

  也就是去目前局部最好的，和過往全局最好的中大的那個（因為最後一次交易如果包含目前天一定在局部最好的裡面，否則一定在過往全局最優的裡面）。對于局部變量的維護，遞推式是

  local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)，

  也就是看兩個量，第一個是全局到i-1天進行j-1次交易，然後加上今天的交易，如果今天是賺錢的話（也就是前面隻要j-1次交易，最後一次交易取目前天），第二個量則是取local第i-1天j次交易，然後加上今天的內插補點（這裡因為local[i-1][j]比如包含第i-1天賣出的交易，是以現在變成第i天賣出，并不會增加交易次數，而且這裡無論diff是不是大于0都一定要加上，因為否則就不滿足local[i][j]必須在最後一天賣出的條件了）。

代碼一

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()){
            return 0;
        }
        int n=prices.size();
        int g[n][3]={0};
        int l[n][3]={0};
        for(int i=1;i<n;i++){
            int diff=prices[i]-prices[i-1];
            for(int j=1;j<=2;j++){
                l[i][j]=max(g[i-1][j-1]+max(diff,0),l[i-1][j]+diff);
                g[i][j]=max(l[i][j],g[i-1][j]);
            }
        }
        return g[n-1][2];
    }
};      

分析二

• 按照參考部落格的思路，buy1記錄的是所有天最便宜的報價，sell1記錄的是所有天隻進行1次買賣的最大利益；buy2表示在第一次獲得最大利益後，再買到那次交易後最便宜股價是剩餘的淨利潤，sell2記錄的是兩次完整交易的最大利潤。

代碼二

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int buy1=INT_MIN;
        int sell1=0;
        int buy2=INT_MIN;
        int sell2=0;
        for(int i=0;i<prices.size();i++){ //每次循環表示進入新的一天
            buy1=max(buy1,-prices[i]);  //記錄之前所有天最便宜的股價
            sell1=max(sell1,buy1+prices[i]);  //記錄之前所有天隻進行1次買賣的最大利益
            buy2=max(buy2,sell1-prices[i]);  //記錄之前天先進行1次交易獲得最大利益後，
                   //再買到那次交易後最便宜股價時剩餘的淨利潤
            sell2=max(sell2,buy2+prices[i]); //記錄之前天進行2次完整交易的最大利潤
        }
        return sell2;
    }
};      

參考文獻