Stock with cooldown

题目描述

解题方法

buy[i] means before day i what is the maxProfit for any sequence end with buy.

sell[i] means before day i what is the maxProfit for any sequence end with sell.

rest[i] means before day i what is the maxProfit for any sequence end with rest.

Solution

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0

        # buy[i] = max(sell[i-2] - prices[i], buy[i-1])
        # sell[i] = max(buy[i-1] + prices[i], sell[i-1])
        length = len(prices)
        if length < 2:
            return 0
        buy = [0 for i in range(3)]
        sell = [0 for j in range(3)]

        buy[0] = -prices[0]
        sell[0] = 0
        buy[1] = max(-prices[0],-prices[1])
        sell[1] = max(0, prices[1] - prices[0])

        for i in range(2, length):
            buy[i%3] = max(sell[(i-2)%3] - prices[i], buy[(i-1)%3])
            sell[i%3] = max(buy[(i-1)%3] + prices[i], sell[(i-1)%3])

        return sell[(length-1)%3]

Reference