You have three possible actions to take each day:
- 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:
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|
So the maximum profit you can get is
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 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)