按策略买卖股票的最佳时机-LeetCode

3652. 按策略购买股票的最佳时机

🎯 问题描述

给你两个整数数组 prices 和 strategy，其中：

• prices[i] 表示第 i 天某股票的价格。
• strategy[i] 表示第 i 天的交易策略，其中：
  • -1 表示买入一单位股票。
  • 0 表示持有股票。
  • 1 表示卖出一单位股票。

同时给你一个 偶数 整数 k，你可以对 strategy 进行 最多一次 修改。一次修改包括：

• 选择 strategy 中恰好 k 个 连续 元素。
• 将前 k / 2 个元素设为 0（持有）。
• 将后 k / 2 个元素设为 1（卖出）。
  利润 定义为所有天数中 strategy[i] * prices[i] 的 总和 。
  返回你可以获得的 最大 可能利润。

说明：

• 这是一个滑动窗口结合前缀和的问题。

• 核心策略：

  • 首先计算不修改任何操作时的基础总利润 base_profit。
  • 利用滑动窗口枚举所有可能的长度为 k 的修改区间。
  • 对于每个窗口，将其分为前半段（长度 k//2）和后半段。
  • 计算“反转后半段操作”后的新收益，并与原收益对比，取最大值。
  • 利用前缀和数组快速计算区间内的策略利润与价格总和。

• 示例：

• 示例 1：

假设 prices = [1, 2, 3, 4], strategy = [1, 1, 1, 1], k = 2
- 基础利润：1+2+3+4 = 10
- 窗口 [0, 1] (k=2, l=1):
  - 原利润 p1: 1+2=3
  - 后半段反转 (位置1): 原为+2，反转为-2。
  - 新窗口利润 p3: 1 (位置0) + (-2) (位置1) = -1
  - 取 max(3, -1) = 3。总利润不变。
- 窗口 [2, 3]:
  - 原利润 p1: 3+4=7
  - 后半段反转 (位置3): 原为+4，反转为-4。
  - 新窗口利润 p3: 3 + (-4) = -1
  - 取 max(7, -1) = 7。
- 最终结果：10

💻 解题思路

思路1：双前缀和 + 滑动窗口

核心逻辑

1. 构建前缀和数组：
   • pre[i+1]：表示前 i 个位置按照 strategy 操作的累积利润。公式：$pre[i+1] = pre[i] + prices[i] \times strategy[i]$。
   • pre_price[i+1]：表示前 i 个位置的价格总和。公式：$pre\_price[i+1] = pre\_price[i] + prices[i]$。
2. 计算基础利润：
   • base_profit = pre[n]，即完全不修改时的总利润。
3. 滑动窗口枚举与优化：
   • 遍历所有可能的窗口起点 i（窗口范围 [i, i+k-1]）。
   • 分割窗口：将窗口分为前半段（长度 l = k//2）和后半段。
   • 计算反转后的利润 p3：
     • 原窗口利润 p1。
     • 反转后半段意味着：原本加上 price，现在减去 price（或者反之）。
     • 变化量 = (新收益) - (旧收益) = $(-val) - (val) = -2 \times val$。
     • 代码中的 p3 计算逻辑实际上是在模拟这种反转带来的总收益变化。
     • 公式解析：p3 = p1 - (原后半段利润) + (后半段价格总和 - 前半段调整)。这里的逻辑稍微复杂，实际上是在计算：前半段保持不变 + 后半段反转后的收益。
   • 更新全局最大值：
     • 总利润 = base_profit - p1 + max(p1, p3)。
     • 即：总利润 = 基础利润 + (优化带来的增量)。

代码实现

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        n = len(prices)
        l = k // 2                     # 前半段长度
        
        # 1. 构建前缀和数组
        # pre[i+1]: 前 i 个位置按 strategy 操作的累积利润
        pre = [0] * (n + 1)
        # pre_price[i+1]: 前 i 个位置的价格总和
        pre_price = [0] * (n + 1)
        
        for i in range(n):
            pre[i+1] = pre[i] + prices[i] * strategy[i]
            pre_price[i+1] = pre_price[i] + prices[i]
        
        # 2. 计算基础总利润
        base_profit = pre[n]
        max_profit = base_profit
        
        # 3. 滑动窗口枚举
        # 枚举每个长度为 k 的窗口 [i, i+k-1]
        for i in range(n - k + 1):
            # 窗口内原策略产生的利润
            p1 = pre[i+k] - pre[i]
            
            # 前半段原利润 (0 到 l-1)
            p_half = pre[i+l] - pre[i] if l > 0 else 0
            
            # 后半段价格和 (l 到 k-1)
            # 用于计算反转后半段时的收益变化
            p_price = pre_price[i+k] - pre_price[i+l]
            
            # 计算修改后的窗口利润 p3
            # 逻辑：
            # 原窗口利润 p1 = 前半段利润 + 原后半段利润
            # 新窗口利润 p3 = 前半段利润 + (反转后的后半段利润)
            p3 = p1 - (pre[i+k] - pre[i+l]) + p_price - p_half
            
            # 整体利润 = 基础总利润 - 窗口内原利润 + 优化后的窗口利润
            candidate = base_profit - p1 + max(p1, p3)
            
            max_profit = max(max_profit, candidate)
        
        return max_profit

📊 性能分析

• 时间复杂度：$O(N)$
  • 构建前缀和数组：$O(N)$。
  • 滑动窗口遍历：$O(N)$，每次窗口内的计算（包括 p3 的推导）都是 $O(1)$。
  • 总体线性时间，能够处理大规模数据。
• 空间复杂度：$O(N)$
  • 使用了两个长度为 $N+1$ 的辅助数组 pre 和 pre_price。

思考

1. 前缀和的双重作用：

   • pre 数组用于快速计算策略收益。
   • pre_price 数组用于快速获取区间内的价格总和，这在涉及“反转操作”（如买入变卖出，收益变化为 $2 \times price$）的计算中非常有用。

2. p3 的公式推导：

   • 代码中的 p3 计算较为晦涩：p1 - (原后半段利润) + p_price - p_half。
   • 这通常对应于题目特定的变换规则。例如，如果题目允许将后半段的“做空”变为“做多”，收益变化不仅仅是取反，还可能涉及价格本身的加减。
   • 理解这一点的关键在于：p_price 代表纯价格加和，而 pre 代表带策略符号的加和。

3. 贪心策略：

   • 算法本质上是在寻找一个“最优区间”进行修改。
   • 对于每个区间，我们只关心修改后是否比不修改更好（max(p1, p3)），这是一种局部贪心，配合全局遍历得到全局最优。

4. 边界处理：

   • l = k // 2 将窗口一分为二。当 k 为奇数时，后半段比前半段多一个元素。
   • 当 l=0 时（即 k=1），前半段为空，代码通过 if l > 0 进行了兼容，保证了逻辑的正确性。