解题思路

这是一道最多进行两次股票交易的问题，主要思路如下：

  1. 问题分析：

    • 可以进行最多两次交易
    • 必须先买入才能卖出
    • 第二次交易必须在第一次交易完成后进行
    • 求最大收益

  2. 解决方案：

    • 使用动态规划，维护四个状态：
      1. : 第一次买入后的最大收益
      2. : 第一次卖出后的最大收益
      3. : 第二次买入后的最大收益
      4. : 第二次卖出后的最大收益

  3. 状态转移：

代码

class Stock {
public:
    int maxProfit(vector<int>& prices, int n) {
        // 初始化四个状态
        int buy1 = -prices[0];  // 第一次买入
        int sell1 = 0;          // 第一次卖出
        int buy2 = -prices[0];  // 第二次买入
        int sell2 = 0;          // 第二次卖出
        
        // 遍历价格序列
        for (int i = 1; i < n; i++) {
            // 更新四个状态
            buy1 = max(buy1, -prices[i]);           // 第一次买入的最大收益
            sell1 = max(sell1, buy1 + prices[i]);   // 第一次卖出的最大收益
            buy2 = max(buy2, sell1 - prices[i]);    // 第二次买入的最大收益
            sell2 = max(sell2, buy2 + prices[i]);   // 第二次卖出的最大收益
        }
        
        return sell2;  // 返回最终的最大收益
    }
};

public class Stock {
    public int maxProfit(int[] prices, int n) {
        // 初始化四个状态
        int buy1 = -prices[0];  // 第一次买入
        int sell1 = 0;          // 第一次卖出
        int buy2 = -prices[0];  // 第二次买入
        int sell2 = 0;          // 第二次卖出
        
        // 遍历价格序列
        for (int i = 1; i < n; i++) {
            // 更新四个状态
            buy1 = Math.max(buy1, -prices[i]);           // 第一次买入的最大收益
            sell1 = Math.max(sell1, buy1 + prices[i]);   // 第一次卖出的最大收益
            buy2 = Math.max(buy2, sell1 - prices[i]);    // 第二次买入的最大收益
            sell2 = Math.max(sell2, buy2 + prices[i]);   // 第二次卖出的最大收益
        }
        
        return sell2;  // 返回最终的最大收益
    }
}

class Stock:
    def maxProfit(self, prices, n):
        # 初始化四个状态
        buy1 = -prices[0]  # 第一次买入
        sell1 = 0          # 第一次卖出
        buy2 = -prices[0]  # 第二次买入
        sell2 = 0          # 第二次卖出
        
        # 遍历价格序列
        for i in range(1, n):
            # 更新四个状态
            buy1 = max(buy1, -prices[i])           # 第一次买入的最大收益
            sell1 = max(sell1, buy1 + prices[i])   # 第一次卖出的最大收益
            buy2 = max(buy2, sell1 - prices[i])    # 第二次买入的最大收益
            sell2 = max(sell2, buy2 + prices[i])   # 第二次卖出的最大收益
        
        return sell2  # 返回最终的最大收益

算法及复杂度

  • 算法：动态规划
  • 时间复杂度： - 只需要遍历一次价格序列
  • 空间复杂度： - 只需要常数个变量存储状态