文章目录

• 一. 题目信息
• • 1. 描述
  • 2. 示例
• 二. 解法
• • 1. 动态规划
  • • ①. 复杂度分析
    • ②. c++解法

一. 题目信息

1. 描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
题目链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

2. 示例

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

二. 解法

1. 动态规划

算法思路：注意理解buy时是上上次出售时

①. 复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

②. c++解法

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN;
        int sel_pre = 0;
        int sel = 0;
        for (int i = 0; i < prices.size(); i++) {
            buy = max(buy, sel_pre - prices[i]);
            sel_pre = sel;
            sel = max(sel_pre, buy + prices[i]);
        }
        return sel;
    }
};