题目理解
给定价格数组prices和策略数组strategy，策略可以是：
-1: 买入0: 持有1: 卖出
利润 = Σ(strategy[i] × prices[i])
我们可以进行最多一次修改：选择连续 k 个元素，前 k/2 个改为 0，后 k/2 个改为 1。
求最大可能利润。
解题思路
方法一：暴力枚举（朴素思路）
最直接的想法是枚举所有可能的修改位置：
- 不修改的情况
- 从索引 0, 1, 2, …, n-k 开始修改
每次计算修改后的总利润，取最大值。
时间复杂度: O(n²) - 枚举 O(n) 个位置，每次重新计算总利润 O(n)
方法二：前缀和优化（推荐）
观察到暴力方法有大量重复计算。我们可以用前缀和优化。
核心思想
设原始利润为base = Σ(strategy[i] × prices[i])
当我们修改从位置 i 开始的 k 个元素时：
修改前: [i, i+1, ..., i+k/2-1, i+k/2, ..., i+k-1] 修改后: [ 全部变成0 ][ 全部变成1 ]设：
p1 = i,p2 = i + k/2 - 1（前半部分，变成 0）p3 = i + k/2,p4 = i + k - 1（后半部分，变成 1）
则：
- 原利润在 [p1, p2] 区间:
base1 = Σ(strategy[j] × prices[j])，修改后变为 0 - 原利润在 [p3, p4] 区间:
base2 = Σ(strategy[j] × prices[j])，修改后变为Σprices[j]
关键公式：
新利润 = base - base1 - base2 + Σprices[p3~p4]即：
profit_diff = Σprices[p3~p4] - base1 - base2只有当profit_diff > 0时，修改才能提升利润。
前缀和预处理
使用两个前缀和数组：
- prefixSums[i]: prices 的前缀和，用于快速计算价格区间和
- baseSums[i]: strategy[j] × prices[j] 的前缀和，用于快速计算原利润
这样每次查询区间和的时间从 O(k) 降到 O(1)。
时间复杂度: O(n) - 预处理 O(n)，枚举 O(n) 个位置，每次 O(1) 计算
空间复杂度: O(n)
代码实现
funcmaxProfit(prices[]int,strategy[]int,kint)int64{n:=len(prices)// 前缀和预处理prefixSums:=make([]int64,n+1)// prices 的前缀和baseSums:=make([]int64,n+1)// strategy[i]*prices[i] 的前缀和varbaseint64fori:=0;i<n;i++{prefixSums[i+1]=prefixSums[i]+int64(prices[i])base+=int64(strategy[i])*int64(prices[i])baseSums[i+1]=baseSums[i]+int64(strategy[i])*int64(prices[i])}// 边界：k > n 时无法修改ifk>n{returnbase}maxProfit:=base// 枚举所有修改起点fori:=0;i<=n-k;i++{p1:=i p2:=i+k/2-1p3:=i+k/2p4:=i+k-1// 原利润中被修改部分的贡献base1:=baseSums[p2+1]-baseSums[p1]base2:=baseSums[p4+1]-baseSums[p3]// 修改后后半部分的贡献（全为1）priceSum:=prefixSums[p4+1]-prefixSums[p3]// 新利润 = 原利润 - 被移除部分 + 新增部分profit:=base-base1-base2+priceSumifprofit>maxProfit{maxProfit=profit}}returnmaxProfit}示例演示
以prices = [4,2,8], strategy = [-1,0,1], k = 2为例：
预处理：
- base = (-1)×4 + 0×2 + 1×8 = 4
- prefixSums = [0, 4, 6, 14]
- baseSums = [0, -4, -4, 4]
枚举修改位置：
i=0: 修改 [0,1] → [0,1,1]
- base1 = baseSums[1] - baseSums[0] = -4
- base2 = 0 (p3=p4+1)
- priceSum = prefixSums[2] - prefixSums[1] = 2
- profit = 4 - (-4) - 0 + 2 =10✓
i=1: 修改 [1,2] → [-1,0,1] (无变化)
- profit = 4
最大利润: 10
复杂度分析
- 时间复杂度: O(n)，其中 n 是数组长度
- 空间复杂度: O(n)，用于存储前缀和数组
总结
本题的关键是识别暴力枚举中的重复计算，通过前缀和实现 O(1) 的区间和查询，将时间复杂度从 O(n²) 优化到 O(n)。这是一个典型的「暴力→优化」的思维过程。
