题解 | #股票交易日#

股票交易日

https://www.nowcoder.com/practice/3e8c66829a7949d887334edaa5952c28?tpId=182&tqId=34405&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj&difficulty=undefined&judgeStatus=undefined&tags=&title=MT10

解题思路

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

问题分析：
- 可以进行最多两次交易
- 必须先买入才能卖出
- 第二次交易必须在第一次交易完成后进行
- 求最大收益
解决方案：
- 使用动态规划，维护四个状态：
  1. $buy1$ : 第一次买入后的最大收益
  2. $sell1$ : 第一次卖出后的最大收益
  3. $buy2$ : 第二次买入后的最大收益
  4. $sell2$ : 第二次卖出后的最大收益
状态转移：
- $buy1 = \max(buy1, -price)$
- $sell1 = \max(sell1, buy1 + price)$
- $buy2 = \max(buy2, sell1 - price)$
- $sell2 = \max(sell2, buy2 + price)$

代码

cpp
java
python

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  # 返回最终的最大收益