文章目录

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

一. 题目信息

1. 描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
题目链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

2. 示例

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

二. 解法

1. 动态规划

算法思路：维护四种状态，推导到最后即为答案

①. 复杂度分析

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

②. c++解法

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy1 = -prices[0];
        int sel1 = 0;
        int buy2 = -prices[0];
        int sel2 = 0;
        for (int i = 1; i < prices.size(); i++) {
            buy1 = max(buy1, -prices[i]);
            sel1 = max(sel1, buy1 + prices[i]);
            buy2 = max(buy2, sel1 - prices[i]);
            sel2 = max(sel2, buy2 + prices[i]);
        }
        return sel2;
    }
};