# C++ DP with O(n) time O(n) space with explanation, very easy to understand

• I know there are solutions which can solve this in O(1) space, but I think my solution is easier to understand.

Brief explanation:
dp[i] means current max profit.
isUsed means whether there is a operation in the previous day.
lastUsedIndex means the last day which has a operation.

And for dp[i], basically there are two condition :

1. just keep the same, dp[i] = dp[i-1]

2. selling the stock in this day:

a: if isUsed = 0, dp[i] = max(dp[i-3] + prices[i] - prices[i-1], dp[lastUsedIndex] + prices[i] - prices[lastUsedIndex]);

b: if isUsed = 1, dp[i] = dp[i-1] + prices[i] - prices[i-1];

class Solution {

``````public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n < 2)
return 0;
vector<int> dp(n, 0);
bool isUsed = 0;
int lastUsedIndex = -1;
for(int i = 1; i < n; i ++) {
int prev = dp[i - 1];
int diff = max(0, prices[i] - prices[i - 1]);
int val;
if(isUsed == 0) {
val = i > 2 ? dp[i - 3] + diff : diff;
if(lastUsedIndex != -1)
val = max(val, dp[lastUsedIndex] + prices[i] - prices[lastUsedIndex]);
} else {
val = dp[i - 1] + diff;
}
if(prev >= val) {
dp[i] = prev;
isUsed = 0;
} else {
dp[i] = val;
isUsed = 1;
lastUsedIndex = i;
}
}
return dp[n- 1];
}
};``````

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