# The State Machine Solution

• You have three possible actions to take each day:

• Sell
• Do nothing

After taking each action, you have three possible states:

• Holding one share
• Cooling down

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

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)
``````

• @oxygenchen 66666！

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

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