5 lines Python, O(n) time, O(1) space


  • 14
    def maxProfit(self, prices):
        free = 0
        have = cool = float('-inf')
        for p in prices:
            free, have, cool = max(free, cool), max(have, free - p), have + p
        return max(free, cool)
    

    free is the maximum profit I can have while being free to buy.
    have is the maximum profit I can have while having stock.
    cool is the maximum profit I can have while cooling down.


  • -1
    W

    If we got {1,2,3,0,2,0,5},the max profit is 6,but when I use your solution on this, the result is 3,is there something wrong?


  • 0

    @WangPuppy

    • {1,2,3,0,2,0,5} is invalid input, do you mean [1,2,3,0,2,0,5]?
    • The max profit for that is 7, not 6.
    • My solution does return 7, not 3.

  • 2
    S

    could you explain the solution more please?


  • 0
    C

    very neat and smart solution!


  • 2
    N

    @StefanPochmann
    This is very smart.

    @stone30
    Let me just expand what StefanPochmann explained a little bit:
    free is the maximum profit I can have while being free to buy. I am free to buy in the current iteration either because I was free to buy in the previous iteration and did nothing in the current iteration, or I was cooling down in the previous iteration and did nothing in the current iteration.
    have is the maximum profit I can have while having stock, i.e., I've bought a stock and haven't sold it yet. This happens when I was already holding stock but did not sell in this iteration, or I was free to buy stock last iteration and bought the stock in the current iteration.
    cool is the maximum profit I can have while cooling down. This only happens if I was holding a stock in the previous iteration and sold it in the current iteration.


  • 1

    Neat solution! Rewrite in Java.

        public int maxProfit(int[] prices) {
            
            int free = 0;
            int have = Integer.MIN_VALUE;
            int cool = Integer.MIN_VALUE;
            
            for(int i = 0; i < prices.length; i++) {
                
                int freeToday = free;
                int coolToday = cool;
                int haveToday = have;
                
                free = Math.max(freeToday, coolToday);
                have = Math.max(haveToday, freeToday - prices[i]);
                cool = haveToday + prices[i];
            }
            
            return Math.max(free, cool);
        }
    

  • 0
    S

    @StefanPochmann smart solution, could you please share the thought process to approach it in this way , basically what did you think of first when you saw the problem . why not do sorting , checking maxima's and minima's but instead you saw this as a multiple assignment problem .


Log in to reply
 

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