python dp solution


  • 0
    Y

    Consider the last transaction till day i, there could be three states:

    1. stock sold, and cooling down
    2. stock sold, not cooling down
    3. stock bought

    state 1-> state 2 after one day.
    state 2-> buy stock-> state 3
    state 2-> not buy-> state 2
    state 3-> sell stock-> state 1
    state 3-> not sell->state 3

    and here we think of the potential of earning:

    • If we buy the stock at day i, the potential decreases by prices[i]. With lower price, we get higher potential.If the we buy the stock at the first day, the potential would be -prices[0].
    • If we sell the stock at day i, the potential increase by prices[i]. With higher sell price, we can get higher potential.
    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            if len(prices)<=1:
                return 0
            sold_and_cooldown=0
            sold_not_cooldown=0
            bought=-prices[0]
            max_profit=0
            for i in range(1,len(prices)):
                sold_and_cooldown,sold_not_cooldown,bought=\
                    bought+prices[i],\
                    max(sold_and_cooldown,sold_not_cooldown),\
                    max(bought,sold_not_cooldown-prices[i])
            return max(sold_and_cooldown,sold_not_cooldown)
    

Log in to reply
 

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