Best time to buy and sell stock with cool down

题目描述

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

解题方法

这一题跟2的区别就是有一天的cooldown不能买stock。4的做法是用local和global来区别在第i天是否有sell的行为， 而这里第i天sell和buy的行为对后面的影响是不同的，所以我们要用两个数组sells和buys来区别

• buys[i]表示在第i天买或者不买达到的最大收益
• sell[i]表示在第i天卖或者不卖达到的最大收益

初始状态

buys = [0 for i in range(length)]
sells = [0 for i in range(length)]

sells[0], sells[1] = 0, max(0, prices[1] - prices[0])
buys[0], buys[1] = -prices[0], max(-prices[0], -prices[1])

function

sells[i] = max(sells[i-1], buys[i-1] + prices[i])
buys[i] = max(buys[i-1], sells[i-2] - prices[i])

Solution

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

        length = len(prices)

        if length < 2:
            return 0

        buys = [0 for i in range(length)]
        sells = [0 for i in range(length)]

        sells[0], sells[1] = 0, max(0, prices[1] - prices[0])
        buys[0], buys[1] = -prices[0], max(-prices[0], -prices[1])

        for i in range(2, length):
            sells[i] = max(sells[i-1], buys[i-1] + prices[i])
            buys[i] = max(buys[i-1], sells[i-2] - prices[i])

        return sells[-1]

Reference

• cooldown