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

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

• + ```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++
  
  ```cpp
  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