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


  • 35

    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> buy(sz, 0);
    	vector<int> sell(sz, 0);
    	buy[0] = -p[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)
    			buy[i] = buy[0] + p[0] - p[1];
    		else
    			buy[i] = max(sell[i - 2] - p[i], buy[i - 1] + p[i - 1] - p[i]);
    	}
    	return ret;
    }

  • 1
    K

    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.


  • -1
    Z

    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();
            vector<int> buy(N), sell(N), cool1(N), cool2(N);
            buy[0] = -prices[0];
            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++){
                printf("%02d\t%02d\t%02d\t%02d\n", buy[i], sell[i], cool1[i], cool2[i]);
            }*/
            int res = max(sell[N-1], cool1[N-1]);
            return res;
        }
    };

  • 0
    C

    Best and most understandable solution for this problem


Log in to reply
 

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