Golang solution DP 3ms with explanation


  • 0
    R

    Basically, you want to keep track of maximum profits in two different states for each price: buy and sell.

    We start off by setting the current buy state (b0) and previous buy state (b1) to negative numbers.
    Next all sell states s0, s1, s2 are set to 0.

    Starting at the 2nd price (we ignore first becase we can't have a profit in 1 day), we decide the maximum profit for buy on this day. We choose between yesterday's buy max profit or buying today (comparing selling 2 days ago + cooldown yesterday). Then, we find max profit for today's sell with yesterday's sell price vs. today's price - buying it from yesterday.

    At the end, we return the last sell price (because that's the last time you could've made a profit. You can't make a profit by buying on the last day)

    func maxProfit(prices []int) int {
        if len(prices) <= 1 {
            return 0
        }
        
        b0 := -prices[0]
        b1 := b0
        s0, s1, s2 := 0, 0, 0
        
        for i:=1; i < len(prices); i++ {
            b0 = b1
            if b1 < s2 - prices[i] {
                b0 = s2 - prices[i]
            }
            s0 = s1
            if s1 < b1 + prices[i] {
                s0 = b1 + prices[i]
            }
            b1 = b0
            s2 = s1
            s1 = s0
        }
        
        return s0
    }
    

Log in to reply
 

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