这道题是 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)TypeScript 实现class FenwickTree {private n: number;private tree: number[];private INF -1e18;constructor(n: number) {this.n n;this.tree new Array(n 2).fill(this.INF);}// 单点取 max 更新update(idx: number, val: number): void {for (; idx this.n; idx idx (-idx)) {this.tree[idx] Math.max(this.tree[idx], val);}}// 前缀最大值查询 [1, idx]query(idx: number): number {let res this.INF;for (; idx 0; idx - idx (-idx)) {res Math.max(res, this.tree[idx]);}return res;}}function maxAlternatingSum(nums: number[], k: number): number {const n nums.length;// 1. 值域离散化const sorted [...new Set(nums)].sort((a, b) a - b);const rankMap new Mapnumber, number();sorted.forEach((v, i) rankMap.set(v, i 1)); // 1-basedconst m sorted.length;// 2. 两棵树状数组// bitDown维护 down 值用于查询值小于当前值的最大 down// bitUpRev维护 up 值倒序坐标用于查询值大于当前值的最大 upconst bitDown new FenwickTree(m);const bitUpRev new FenwickTree(m);const up new Array(n).fill(0);const down new Array(n).fill(0);let ans 0;const INF -1e18;for (let i 0; i n; i) {// 3. 延迟激活把 i-k 位置的状态加入树状数组if (i k) {const prev i - k;const prevRank rankMap.get(nums[prev])!;bitDown.update(prevRank, down[prev]);bitUpRev.update(m - prevRank 1, up[prev]); // 倒序映射后缀变前缀}const curRank rankMap.get(nums[i])!;// 4. 状态转移// up[i]前一个值 nums[i]从 bitDown 查询值域 [1, curRank-1] 的最大 downconst bestDown bitDown.query(curRank - 1);up[i] nums[i] (bestDown INF ? 0 : bestDown);// down[i]前一个值 nums[i]从 bitUpRev 查询值域 [curRank1, m] 的最大 upconst bestUp bitUpRev.query(m - curRank);down[i] nums[i] (bestUp INF ? 0 : bestUp);ans Math.max(ans, up[i], down[i]);}return ans;}关键点解析- 值域离散化用 Set 去重后排序建立值到排名的映射压缩值域到 [1, m]树状数组大小可控- 延迟激活这是处理下标距离 ≥ k的关键技巧——遍历时不立即把当前状态加入树状数组而是等 k 步后再加入这样查询时自然只看到距离 ≥ k 的前驱状态- 后缀查询技巧树状数组天然支持前缀查询要查值大于当前值的最大值把排名 r 反转为 m - r 1就把后缀查询变成了前缀查询- 时间复杂度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这类题的通用模板整理出来吗