DP，we can create two array, buy and sell. buy[i] means we buy a stock at day i , and sell[i] means we sell a stock at day i.
so, we have two equations :
- buy[i] = max(buy[i-1] , sell[i-2] - prices[i]) // So we should use sell[i-2] means we cooldown one day.
- sell[i] = max(sell[i-1],buy[i-1] + prices[i])
finally, return the max(buy[n-1] , sell[n-1]) （it is obvious that sell[n-1] >= buy[n-1] ,so we return sell[n-1]）
if you want to see more about it, you can visit my blog : Best Time to Buy and Sell Stock with Cooldown
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ if not prices or len(prices) < 2: return 0 n = len(prices) buy, sell =  * n,  * n buy = -prices buy = max(-prices, -prices) sell = max(0, prices - prices) for i in xrange(2, n): buy[i] = max(sell[i - 2] - prices[i], buy[i - 1]) sell[i] = max(buy[i - 1] + prices[i], sell[i - 1]) return sell[n - 1]
I like this solution. It is quite similar to my thinking process.
(1) You can do it in O(1) space, since
i rely on only
i-2, but I think you know it :-)
(2) The return line, it is always true that
buy[n-1] <= sell[n-1]