**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.