Problem


Key Idea

There exists 3 states, and that can be expressed like this:

Hence, we can use dynamic programming approach to this problem, representing state transfers.

  • holding[i] = max( holding[i-1] , notHolding[i-1] - prices[i])
  • notHolding[i] = max( notHolding[i-1] , cooldown[i-1] )
  • cooldown[i] = holding[i-1] + prices[i]

Initializing base case shouldn’t be difficult,

  • holding[0] = -prices[0]
  • notHolding[0] = 0
  • cooldown[0] = \(-\infty\)

The ultimate answer is \(\max(cooldown[n-1], notHolding[n-1])\).

  • Time: \(O(N)\)
  • Space: \(O(N)\)


Note
We can optimize space complexity into \(O(1)\). Implementation below does that.

Implementation

typedef vector<int> vi;

class Solution {
private:
    const int NEG_INF= -1e7;
public:
    int maxProfit(vi &prices) {
        int n= prices.size(), holding= -prices[0], notHolding= 0, cooldown= NEG_INF;
        for (int i=1; i < n; ++i) {
            int prevHolding= holding;
            holding= max(holding, notHolding-prices[i]);
            notHolding= max(notHolding, cooldown);
            cooldown= prevHolding+prices[i];
        }
        return max(cooldown, notHolding);
    }
};

Leave a comment