309.最佳买卖股票时机含冷冻期

【LetMeFly】309.最佳买卖股票时机含冷冻期

力扣题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

 

提示：

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

方法一：动态规划

力扣上之前关于股票买卖的类似的题目：

• 0121.买卖股票的最佳时机
• 0122.买卖股票的最佳时机II
• 0123.买卖股票的最佳时机III
• 0188.买卖股票的最佳时机IV

本题中，我们使用三个变量：

• buy：手里有一支买了的股票的最大收益
• sell：今天卖了一只股票的最大收益
• none：今天什么都不干的最大收益

第一天，三者的初始值分别为：

• buy：第一天就买入了股票，收益为- 第一天的股票价格
• sell：第一天就卖出了股票（买入的当天卖出），收益为0
• none：第一天什么也不干，收益为0

之后从第二天开始遍历每一天，并计算三者的新值：

• newBuy：今天买入了股票（前提是昨天什么都没干）none - prices[i]，或者之前就买入了股票并且还没卖buy
• newSell：今天卖出了股票（前提是之前有买入股票）buy + prices[i]
• newNone：今天什么都没干并且昨天什么都没干none，或者今天什么都没干并且昨天卖出了一支股票sell

不断更新三者的值，最终返回三者的最大值即可。

• 时间复杂度$O(n)$，其中$n$是股市开放天数
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = -prices[0];
        int sell = 0;
        int none = 0;
        int n = prices.size();
        for (int i = 1; i < n; i++) {
            int newBuy = max(buy, none - prices[i]);
            int newSell = buy + prices[i];
            int newNone = max(none, sell);
            buy = newBuy;
            sell = newSell;
            none = newNone;
        }
        return max(sell, none);
    }
};

Python

# from typing import List

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

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126913940