Share my python solution with explanation


  • 2

    DP,we can create two array, buy and sell. buy[i] means we buy a stock at day i , and sell[i] means we sell a stock at day i.

    so, we have two equations :

    • buy[i] = max(buy[i-1] , sell[i-2] - prices[i]) // So we should use sell[i-2] means we cooldown one day.
    • sell[i] = max(sell[i-1],buy[i-1] + prices[i])

    finally, return the max(buy[n-1] , sell[n-1]) (it is obvious that sell[n-1] >= buy[n-1] ,so we return sell[n-1])

    if you want to see more about it, you can visit my blog : Best Time to Buy and Sell Stock with Cooldown

    class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices or len(prices) < 2: return 0
        n = len(prices)
        buy, sell = [0] * n, [0] * n
        buy[0] = -prices[0]
        buy[1] = max(-prices[0], -prices[1])
        sell[1] = max(0, prices[1] - prices[0])
        for i in xrange(2, n):
            buy[i] = max(sell[i - 2] - prices[i], buy[i - 1])
            sell[i] = max(buy[i - 1] + prices[i], sell[i - 1])
    
        return sell[n - 1]
    

  • 0

    I like this solution. It is quite similar to my thinking process.

    Two comments:

    (1) You can do it in O(1) space, since i rely on only i-1 and i-2, but I think you know it :-)

    (2) The return line, it is always true that buy[n-1] <= sell[n-1]


  • 0

    thanks for you second comments ~ haha~


Log in to reply
 

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