The State Machine Solution


  • 0
    O

    You have three possible actions to take each day:

    • Buy
    • Sell
    • Do nothing

    After taking each action, you have three possible states:

    • Holding one share
    • Sold your stock
    • Cooling down

    Since you must cool-down for one day after selling your stock, we can draw a state transfer diagram like this:

    0_1523513272350_state-dgram.png

    Let's say you have zero dollars at the beginning, and you can have a negative balance on your account. Apparently, the maximum profit you can get is the maximum balance on the final day.

    So we can easily derivate the state transfer equations:

    hold_nextday = max(hold_today, idle_today - prices[today])
    sold_nextday = hold_today + prices[today]
    idle_nextday = max(sold_today, idle_today)
    

    Assume the prices goes like this [1, 2, 3, 0, 2], we can use a table to track your maximum balance each day.

    Day 0 Day 1 Day 2 Day 3 Day 4
    Hold -1 -1 -1 1 1
    Sold 0 1 2 -1 3
    Idle 0 0 1 2 2

    So the maximum profit you can get is 3.

    And the program goes like this:

    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            
            if not prices:
                return 0
            
            hold = -prices[0]
            sold = 0
            idle = 0
            
            for price in prices[1:]:
                hold, sold, idle = max(hold, idle - price), hold + price, max(sold, idle)
            
            return max(hold, sold, idle)
    

  • 0
    E

    @oxygenchen 66666!


  • 0
    H

    @Elfsong 看到666我就知道是中国老铁了


Log in to reply
 

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