Let `dp[i] := the maximum profit you can get from day 0 to day i`

. Separate it into two cases:

- Don't sell in day i:
`dp[i] = dp[i-1]`

- Do sell in day i:
`dp[i] = max{ p[i] - p[j] + dp[j-2] | j is in [0, i-1] }`

.

Hence`dp[i] = p[i] + max{ dp[j-2] - p[j] | j is in [0, i-1] }`

.

So, `dp[i] = max(dp[i-1], p[i] + max{ dp[j-2] - p[j] | j is in [0, i-1] })`

.

In the code below, I use `localMax`

to save to current `max{ dp[j-2] - p[j] | j is in [0, i-1] }`

.

```
// O(n) time, O(n) space
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) return 0;
int N = prices.size(), localMax = INT_MIN;
vector<int> dp(N, 0);
for (int i = 0; i < N; ++i) {
dp[i] = max((i >= 1 ? dp[i - 1] : 0), prices[i] + localMax);
localMax = max(localMax, (i >= 2 ? dp[i - 2] : 0) - prices[i]);
}
return dp[N - 1];
}
};
```

Notice that `dp[i]`

only depends on`dp[i-1]`

and `dp[i-2]`

. So you can simplify the dp array into two variables.

```
// O(n) time, O(1) space
class Solution {
public:
int maxProfit(vector<int>& prices) {
int N = prices.size(), localMax = INT_MIN, ans = 0, prev1 = 0, prev2 = 0;
for (int i = 0; i < N; ++i) {
ans = max(prev1, prices[i] + localMax);
localMax = max(localMax, prev2 - prices[i]);
prev2 = prev1;
prev1 = ans;
}
return ans;
}
};
```