10 line constant space O(n) complexity dp solution in c++ (4ms) [added explanation]


  • 18
    W

    Four states are used for the dp: buy, sell, coolDown and noOp, where noOp happens between buy and sell, coolDown happens between sell and buy.

    It is actually much more straight forward if you use O(n) space.

    buy[i] -- buy stock i

    sell[i] -- sell stock i

    noOp[i] -- no operation for stock i, but have one stock at hand

    coolDown[i] -- no operation for stock i, and have no stock at hand.

    Then the update works as buy[i] = coolDown[i-1]-prices[i], coolDown[i] = max(coolDown[i-1], sell[i-1]), noOp[i] = max[noOp[i-1], buy[i-1]]] and sell[i] = max(noOp[i-1], buy[i-1]) + prices[i].

    The constant space solution readily follows this since current states for price i only depends on previous states for price i-1.

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int buy = INT_MIN, noOp = INT_MIN;
            int coolDown = 0, sell = 0;
            for (int p : prices) {
                noOp = max(noOp, buy);
                buy = coolDown - p;
                coolDown = max(coolDown, sell);
                sell = noOp + p;
            }
            return max(coolDown, sell);
        }
    };

  • 0
    G

    Can you please explain how to work out the solution?


  • 0
    C
    public class Solution {
        public int maxProfit(int[] prices) {
            int buy = Integer.MIN_VALUE, noact = Integer.MIN_VALUE, sell = 0, cooldown = 0;
            for (int price : prices) {
                int pre = sell;
                sell = Math.max(sell, noact + price);
                buy = cooldown - price;
                noact = Math.max(noact, buy);
                cooldown = pre;
            }
            return sell;
        }
    }
    

    Here's my java version code which is inspired by this solution but slightly different.
    sell represents the profit obtained by selling the stock at time [i], also represents the largest profit;
    buy represents the profit obtained by buying the stock at time [i], we can only buy after a cooldown;
    noact represents the profit obtained by keep a hold a stock at time [i], it always holds the least price to buy a stock;
    cooldown represents the profit obtained by doing nothing at time[i], it always follow the trace of sell in [i - 1];


  • 0
    W

    It is actually much more straight forward if you use O(n) space. Then the update works as buy[i] = coolDown[i-1]-prices[i], coolDown[i] = max(coolDown[i-1], sell[i-1]), noOp[i] = max[noOp[i-1], buy[i-1]]] and sell[i] = max(noOp[i-1], buy[i-1]) + prices[i].

    I have added more explanations in the post, let me know if you think this is helpful.


  • 0
    L

    There is no need to use a extra argument buy_prev. Just change the order.
    noOp = max(buy, noOp);
    buy = coolDown - p;
    coolDown = max(coolDown, sell);
    sell = noOp + p;


  • 0
    W

    You are absolutely right. Thank you!


  • 0
    1

    could tell me why int buy = INT_MIN, noOp = INT_MIN;
    int coolDown = 0, sell = 0;

    I wonder how they were initialized


  • 0
    W

    They are boundary conditions that fit into the dp solution. If you think it is easier to understand, you can initialize using the first and second price and then it follows through the iterations for later prices. But it is much neater to fit in a working boundary condition for a virtual price before price[0]. coolDown and sell are 0 since you have no stocks, the profit should be zero. buy and noOp are set to INT_MIN so that it is not possible to sell or noOp the first stock, but it is possible to cooldown or buy the first stock.


  • 0
    1

    Got it!Thank you ! It's really a cool solution!


  • 0
    W

    It is by definition. NoOp is a no-operation state where you have bought a stock, but have not sold it, this is different from a cooldown state, where you have no stock at hand and not plan to buy the current stock.


  • 0
    This post is deleted!

  • 0
    W

    I am not sure what your question. But I think maybe your definition of sell is different from mine. My sell[i] means sell a stock at i. sell[i] = max(noOp[i-1], buy[i-1]) + prices[i]. The code itself requires some massage of the formula that I provided. Hope this helps.


Log in to reply
 

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