123. best time buy and sell stock III

Posted on |

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.

这题标准解法还是用2维dp做,对于每天定义4个变量,第一次买/卖,第二次买/卖.他们之间的递推关系也很容易推出(见代码).然后由于i状态只取决于i-1状态,可以将空间复杂度降低到O(n)(1维dp).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp[2][4] = {INT_MIN, 0, INT_MIN, 0};  // sometime using array is easier than vector
        int cur = 0, next = 1;
        for(int i = 0; i < prices.size(); i++){
            dp[next][0] = max(dp[cur][0], -prices[i]);
            dp[next][1] = max(dp[cur][1], dp[cur][0] + prices[i]);
            dp[next][2] = max(dp[cur][2], dp[cur][1] - prices[i]);
            dp[next][3] = max(dp[cur][3], dp[cur][2] + prices[i]);
            swap(cur, next); // a tricky strategy for swaping cur and next
        }
        return max(dp[cur][1], dp[cur][3]); // remember to compare 1 time trade with 2 time trade

    }
};

Even better, 我们可以只用4个变量(或者1维数组)来求解.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    int maxProfit(vector<int>& prices) {
        int hold1 = INT_MIN, hold2 = INT_MIN;
        int release1 = 0, release2 = 0;
        for(int i : prices){
            release2 = max(release2, hold2+i);     // The maximum if we've just sold 2nd stock so far.
            hold2    = max(hold2,    release1-i);  // The maximum if we've just buy  2nd stock so far.
            release1 = max(release1, hold1+i);     // The maximum if we've just sold 1nd stock so far.
            hold1    = max(hold1,    -i);          // The maximum if we've just buy  1st stock so far.
        }
        return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
    }
}