C++ DP with O(n) time O(n) space with explanation, very easy to understand


  • 2
    S

    I know there are solutions which can solve this in O(1) space, but I think my solution is easier to understand.

    Brief explanation:
    dp[i] means current max profit.
    isUsed means whether there is a operation in the previous day.
    lastUsedIndex means the last day which has a operation.

    And for dp[i], basically there are two condition :

    1. just keep the same, dp[i] = dp[i-1]

    2. selling the stock in this day:

      a: if isUsed = 0, dp[i] = max(dp[i-3] + prices[i] - prices[i-1], dp[lastUsedIndex] + prices[i] - prices[lastUsedIndex]);

      b: if isUsed = 1, dp[i] = dp[i-1] + prices[i] - prices[i-1];

    class Solution {

    public:
        int maxProfit(vector<int>& prices) {
            int n = prices.size();
            if(n < 2)
                return 0;
            vector<int> dp(n, 0);
            bool isUsed = 0;
            int lastUsedIndex = -1;
            for(int i = 1; i < n; i ++) {
                int prev = dp[i - 1];
                int diff = max(0, prices[i] - prices[i - 1]);
                int val;
                if(isUsed == 0) {
                    val = i > 2 ? dp[i - 3] + diff : diff;
                    if(lastUsedIndex != -1)
                        val = max(val, dp[lastUsedIndex] + prices[i] - prices[lastUsedIndex]);
                } else {
                    val = dp[i - 1] + diff;
                }
                if(prev >= val) {
                    dp[i] = prev;
                    isUsed = 0;
                } else {
                    dp[i] = val;
                    isUsed = 1;
                    lastUsedIndex = i;
                }
            }
            return dp[n- 1];
        }
    };

Log in to reply
 

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