题目

309. Best Time to Buy and Sell Stock with Cooldown

解法

１、假定三个状态buy, sell, cool，分别表示当前时刻有物品在手(buy)，出售物品(sell)，什么也不做(cool)。
２、
当前处于buy的情况有两种：上一个时刻处于buy状态，当前时刻仍然维持该状态；上一个时刻处于cool状态，当前时刻买入商品。
当前处于cool的情况两种：上一个时刻出售商品(sell)，当前cool；上一个时刻为cool，当前仍为cool。
当前处于sell的只有一种情况：上一个时刻为buy，当前sell。
３、确定每个时刻各状态的最优值并保存。示意图如下所示。

流程图

代码如下

    def maxProfit(self, prices: List[int]) -> int:
        buy = float('-inf')
        cool = 0
        sell = 0
        for p in prices:
            buy = max(buy, cool-p)
            cool = max(cool, sell)
            sell = buy+p
        return max(cool, sell)