# O(n) time, O(1) space C++ DP and thinking process

• Let `dp[i] := the maximum profit you can get from day 0 to day i`. Separate it into two cases:

1. Don't sell in day i: `dp[i] = dp[i-1]`
2. 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;
}
};
``````

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