題目描述

給定一個整數(shù)數(shù)組，其中第 i 個元素代表了第 i 天的股票價格 。?

設(shè)計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

• 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
• 賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

示例 1:

輸入: [1,2,3,0,2]
輸出: 3
解釋: 對應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]

解法

參考：Leetcode 121. 買賣股票的最佳時機

有如下遞推關(guān)系式：

這里的 表示前一天不持有股票，并且再前一天也不持有股票，即當(dāng)天不處于冷卻期，可以買入股票。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        lastI0,i0,i1=0,0,-prices[0]
        for i in range(1,len(prices)):
            lastI0,i0,i1=i0,max(i0,i1+prices[i]),max(i1,lastI0-prices[i])
        return i0