这道题是 LeetCode 3915「距离至少为 K 的交替子序列的最大和」核心思路是 DP 值域离散化 树状数组Fenwick Tree优化将复杂度从 O(n²) 降到 O(n log n)。题目理解给定数组 nums 和整数 k选一个下标严格递增的子序列满足1. 相邻选中下标之差 ≥ k2. 选出的值严格交替小大 或 大小 波动不能相等3. 求最大和核心思路1. DP 状态up[i] 表示以 nums[i] 结尾、最后一步是递增前一个值 当前值的最大和down[i] 表示以 nums[i] 结尾、最后一步是递减的最大和2. 转移逻辑- up[i] nums[i] max{down[j]}其中 j ≤ i-k 且 nums[j] nums[i]- down[i] nums[i] max{up[j]}其中 j ≤ i-k 且 nums[j] nums[i]3. 延迟激活只有当 i ≥ k 时才把 i-k 位置的状态加入树状数组保证下标距离 ≥ k4. 树状数组优化用两棵树状数组分别维护值小于当前值和值大于当前值的最大 DP 值查询/更新均为 O(log n)Rust 实现use std::cmp::max;use std::collections::BTreeSet;struct FenwickTree {n: usize,tree: Veci64,}impl FenwickTree {fn new(n: usize) - Self {FenwickTree {n,tree: vec![i64::MIN / 2; n 2], // 初始化为极小值}}// 单点取 max 更新fn update(mut self, mut idx: usize, val: i64) {while idx self.n {self.tree[idx] max(self.tree[idx], val);idx idx idx.wrapping_neg(); // idx idx (-idx)}}// 前缀最大值查询 [1, idx]fn query(self, mut idx: usize) - i64 {let mut res i64::MIN / 2;while idx 0 {res max(res, self.tree[idx]);idx - idx idx.wrapping_neg();}res}}impl Solution {pub fn max_alternating_sum(nums: Veci32, k: i32) - i64 {let n nums.len();let k k as usize;// 1. 值域离散化let mut sorted: Veci32 nums.clone();sorted.sort();sorted.dedup();let m sorted.len();// 2. 两棵树状数组// bit_down维护 down 值用于查询值小于当前值的最大 down// bit_up_rev维护 up 值倒序坐标用于查询值大于当前值的最大 uplet mut bit_down FenwickTree::new(m);let mut bit_up_rev FenwickTree::new(m);let mut up vec![0i64; n];let mut down vec![0i64; n];let mut ans 0i64;for i in 0..n {// 3. 延迟激活把 i-k 位置的状态加入树状数组if i k {let prev i - k;let prev_rank sorted.binary_search(nums[prev]).unwrap() 1; // 1-basedbit_down.update(prev_rank, down[prev]);bit_up_rev.update(m - prev_rank 1, up[prev]); // 倒序映射后缀变前缀}let cur_rank sorted.binary_search(nums[i]).unwrap() 1; // 1-based// 4. 状态转移// up[i]前一个值 nums[i]从 bit_down 查询值域 [1, cur_rank-1] 的最大 downlet best_down bit_down.query(cur_rank - 1);up[i] nums[i] as i64 if best_down i64::MIN / 2 { 0 } else { best_down };// down[i]前一个值 nums[i]从 bit_up_rev 查询值域 [cur_rank1, m] 的最大 uplet best_up bit_up_rev.query(m - cur_rank);down[i] nums[i] as i64 if best_up i64::MIN / 2 { 0 } else { best_up };ans max(ans, max(up[i], down[i]));}ans}}关键点解析- 值域离散化nums[i] 最大 10⁵但实际不同值最多 n 个离散化后压缩到 [1, m]树状数组大小可控- 延迟激活这是处理下标距离 ≥ k的关键技巧——遍历时不立即把当前状态加入树状数组而是等 k 步后再加入这样查询时自然只看到距离 ≥ k 的前驱状态- 后缀查询技巧树状数组天然支持前缀查询要查值大于当前值的最大值把排名 r 反转为 m - r 1就把后缀查询变成了前缀查询- Rust 特有注意点idx (-idx) 在 Rust 中需要用 idx idx.wrapping_neg() 来避免无符号整数的取负溢出问题树状数组初始值设为 i64::MIN / 2 防止加法溢出- 时间复杂度O(n log n)空间 O(n)示例验证- nums [5,4,2], k 2选下标 [0,2]值 [5,2]距离 2-02≥k52 严格交替得分 7 ✅- nums [3,5,4,2,4], k 1选下标 [0,1,3,4]值 [3,5,2,4]3524 严格交替得分 14 ✅- nums [5], k 1长度为 1 始终有效得分 5 ✅需要我把树状数组优化 DP 的通用模板整理出来吗