Consider the last transaction till day i, there could be three states:
- stock sold, and cooling down
- stock sold, not cooling down
- 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.
- 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 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)