O(n) time, O(1) space C++ DP and thinking process


  • 0

    Let dp[i] := the maximum profit you can get from day 0 to day i. Separate it into two cases:

    1. Don't sell in day i: dp[i] = dp[i-1]
    2. Do sell in day i: dp[i] = max{ p[i] - p[j] + dp[j-2] | j is in [0, i-1] }.
      Hence dp[i] = p[i] + max{ dp[j-2] - p[j] | j is in [0, i-1] }.

    So, dp[i] = max(dp[i-1], p[i] + max{ dp[j-2] - p[j] | j is in [0, i-1] }).

    In the code below, I use localMax to save to current max{ dp[j-2] - p[j] | j is in [0, i-1] }.

    // O(n) time, O(n) space
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if (prices.empty()) return 0;
            int N = prices.size(), localMax = INT_MIN;
            vector<int> dp(N, 0);
            for (int i = 0; i < N; ++i) {
                dp[i] = max((i >= 1 ? dp[i - 1] : 0), prices[i] + localMax);
                localMax = max(localMax, (i >= 2 ? dp[i - 2] : 0) - prices[i]);
            }
            return dp[N - 1];
        }
    };
    

    Notice that dp[i] only depends ondp[i-1] and dp[i-2]. So you can simplify the dp array into two variables.

    // O(n) time, O(1) space
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int N = prices.size(), localMax = INT_MIN, ans = 0, prev1 = 0, prev2 = 0;
            for (int i = 0; i < N; ++i) {
                ans = max(prev1, prices[i] + localMax);
                localMax = max(localMax, prev2 - prices[i]);
                prev2 = prev1;
                prev1 = ans;
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.