# An 8ms C++ DP solution, easy to understand

• I think my solution is not very difficult to understand.

Define `buy[i]` as the max profit when you buy the stock at day i. `sell[i]` as the max profit when you sell the stock at day i. Therefore set `buy[0] = -prices[0]`, that if you buy the stock at first day, the profit is -prices[0], also set `sell[0] = 0`, that you do nothing in the first day.

``````sell[i]=max(buy[i-1]+prices[i], sell[i-1]-prices[i-1]+prices[i]);
``````

`buy[i-1]+prices[i]` represents buy the stock on day i-1 and sell it on day i; `sell[i-1]-prices[i-1]+prices[i]` represents you didn't sell the stock on day i-1 but sell it on day i (bought stock back and sell it on day i).

``````buy[i]=max(sell[i-2]-prices[i], buy[i-1]+prices[i-1]-prices[i]);
``````

`sell[i-2]-prices[i]` means sold the stock on day i-2 and buy it on day i (day i-1 is cooldown). `buy[i-1]+prices[i-1]-prices[i]` means you didn't buy the stock on day i-1 but buy it on day i.

No doubt that the max profit would appear in sell[i].

``````int maxProfit(vector<int>& p)
{
if (p.size() < 2)
return 0;
int i, sz = p.size();
int ret = 0;
vector<int> sell(sz, 0);
for (i = 1; i < sz; ++i)
{
sell[i] = max(buy[i - 1] + p[i], sell[i - 1] - p[i - 1] + p[i]);
if (ret < sell[i]) //record the max sell[i]
ret = sell[i];
if (1 == i)
else
buy[i] = max(sell[i - 2] - p[i], buy[i - 1] + p[i - 1] - p[i]);
}
return ret;
}``````

• Just trying to understand these formulas. I don't quite get your explanation about the physical meaning of sell[i] and buy[i]. I gave mine below to see whether I have the correct understanding.

(1) sell[i] consists of two conditions and all based on you have a stock before i (except day 0)

(a). You just have it yesterday, and sell it today.

(b). You have it before yesterday, say on day x where x<i-1, and you did not sell it until day i. since the profit after buying the at day x is buy[x] = sell[i] - prices[i] = price[i-1] - prices[i-1], then we can conclude sell[i] = price[i-1] - prices[i-1] + prices[i]

(2) buy[i] consists of two conditions as well and all based on you do not hold any stock before day i-2.

(a). You just sold it on i-2.

(b). You sold stock before i-2, Say you sell on day x and you did not buy anything until you buy at day i. where sell[x] = buy[i] + prices[i] = buy[i-1]+prices[i-1] and you get second part.

I try to explain the way that how we divide the time series and in this way, I could understand that all conditions are covered.

• Here's my 9ms C++ DP solution.

There are four states for each day: buy, sell, cool1, cool2.
The O(n) memory could be optimized to O(1) since each step's calculation depends only on the previous step.

``````class Solution {
public:
/**
*      buy[i] = cool1[i-1] - prices[i]; //the max profit if buy at i
*      sell[i] = max(buy[i-1], cool2[i-1]) + prices[i]; //the max profit if sell at i
*      cool1[i] =  max(cool1[i-1], sell[i-1]); //the max profit if cool(don't hold stock) at i
*      cool2[i] =  max(cool2[i-1], buy[i-1]); //the max profit if cool(hold stock) at i
*/
int maxProfit(vector<int>& prices) {
if(prices.size()<=1)
return 0;
const int N = prices.size();
sell[0] = numeric_limits<int>::min();
cool1[0] = 0;
cool2[0] = numeric_limits<int>::min();
for(int i=1; i<N; i++){
buy[i] = cool1[i-1] - prices[i]; //the max profit if buy at i
sell[i] = max(buy[i-1], cool2[i-1]) + prices[i]; //the max profit if sell at i
cool1[i] =  max(cool1[i-1], sell[i-1]); //the max profit if cool(don't hold stock) at i
cool2[i] =  max(cool2[i-1], buy[i-1]); //the max profit if cool(hold stock) at i
}
/*for(int i=0; i<N; i++){