# Very simple explanation based basic math, (no state machine etc. ) O(N) DP code attached

• Define `profit[i]` - maximum profit can be made on day i following the cool down rule

`profit[i] = Max(prices[i]-prices[j] + profit[j-2])` for `all j < i` (1)

• `prices[i]-prices[j]` buying on j and sell on i (1.1)
• `profit[j-2]` accumulated profit from 0 to j-2 (1.2)

Above calculation would lead to O(N^2) complexity, let's simplify using linearity

`profit[i] = Max(prices[i]) + Max(profit[j-2]-prices[j])` for all `j<i` (2)

• `Max( prices[i] ) = prices[i]` is O(1) calculation
• `Max(profit[j-2]-prices[j])` for `all j<i` is O(1) calculation

This is O(N), below is the code

``````public int maxProfit(int[] prices) {
int n = prices.length;
if(n<=1) return 0;
int[] dp = new int[n + 1];
int max = -prices[0];
for (int i = 1; i < n; i++) {
dp[i + 1] = Math.max(dp[i], max + prices[i]);
max = Math.max(dp[i - 1] - prices[i], max);
}

return dp[n];
}
``````

Of course this post is here to illustrate the concept of DP, the space can further be optimized into O(1). Plus, if you read the other posts with state machines and buy,sell,cool down states, it's all reduces into this format. The only difference if how you explain the variables you define in each case.

• I think the formula should be

profit[i] = Max(prices[i]-prices[j] + profit[j-2], profit[i-1]) for all j < i (1), it can be changed to:

profit[i] = Max( prices[i] + max(profit[j-2]-prices[j]), profit[i-1] ) for all j<i (2)

select profit[i-1] means sell stock on day i-1 and do nothing on day i

prices[i]-prices[j] means buying on day j and sell on day i

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