 ## 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 = -prices
• notHolding = 0
• cooldown = $$-\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, 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);
}
};


Tags:

Updated: