题目

给一个数组代表每天的股价，求获益最大为多少。
限制：

• 一次只能持有一只股票。
• 卖掉股票之后，第二天不能购买，第三天之后才可购买股票。

思路

又是一个典型的动态规划问题。分两种状态:

• 最后一次操作是购买的情况下，前i天的最大获利为buy[i]
• 最后一次操作是售出的情况下，前i天的最大获利为sell[i]

状态转移如下：

• 要求最后一次为购买的前i天最大获利buy[i]，分两种情况：

  1. 第i天购买，则在i-2天之前已售出，需要找出前i-2天最后一次是售出的最大获利sell[i-2]，再减去购买当日的价格price[i]。
  2. 不购买，与前一天获利相同，即buy[i-1]

  因此buy[i] = max(sell[i-2] - price[i], buy[i-1])

• 同理，根据最后一天是否出售，可以将sell[i]的求取分两种情况，去最大值，即sell[i] = max(buy[i-1]+price[i], sell[i-1])

最后求得sell[n]即为所求。

代码

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) < 2:
            return 0
        sell = [0] * len(prices)
        buy = [-prices[0]] * len(prices)
        for i in range(1, len(prices)):
            buy[i] = max(buy[i-1], sell[i-2] - prices[i])
            sell[i] = max(sell[i-1], buy[i-1] + prices[i])
        return sell[len(prices)-1]