# An easy dp solution with explaination

• ``````/*
* dp solution: O(n) time, O(n) space
* unkeep stock status
*      sellDP[i] = max(sellDP[i-1], buyDP[i-1] + prices[i]);
*
*   keep stock status
*      buyDP[i] = max(buyDP[i-1], sellDP[i-2] - prices[i]);
*/
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n <= 1) return 0;
vector<int> sellDP(n, 0), buyDP(n, 0);
buyDP[0] = -prices[0];

for (int i = 1; i < n; ++i) {
sellDP[i] = max(sellDP[i-1], buyDP[i-1] + prices[i]);
if (i >= 2) buyDP[i] = max(buyDP[i-1], sellDP[i-2] - prices[i]);
else buyDP[i] = max(buyDP[i-1], -prices[i]);
}

return sellDP[n-1];
}

/*
* ==> dp solution
* ==> deducted to O(n) time, O(1) space
*/
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n <= 1) return 0;

int curSell = 0; // current day, yesterday
int preSell = 0; // the day before yesterday
int curBuy = -prices[0]; // current day, yesterday
for (int i = 1; i < n; ++i) {
int tmp = curSell;
curSell = max(curSell, curBuy + prices[i]);
if (i >= 2) curBuy = max(curBuy, preSell - prices[i]);
else curBuy = max(curBuy, -prices[i]);
preSell = tmp;
}

return curSell;
}``````

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