这是 LeetCode 3915 Maximum Sum of Alternating Subsequence With Distance at Least K周赛 499 Q4难度 HardRating 2288。题目理解- 从 nums 中选一个子序列相邻下标距离 k。- 子序列的值必须严格交替 ... 或 ...。- 单元素子序列也算交替。- 求最大和。核心思路DP 树状数组值域设 dp[i][0] 表示以 i 结尾、最后一个元素是谷下一个必须更大的最大和dp[i][1] 表示最后一个元素是峰下一个必须更小的最大和。转移时需要找满足 j i - k 的前驱 j- dp[i][0]谷要求 nums[j] nums[i]从 dp[j][1] 转移。- dp[i][1]峰要求 nums[j] nums[i]从 dp[j][0] 转移。这需要在值域上做前缀/后缀最大值的动态查询用两个树状数组维护- bit0维护 dp[j][0] 的前缀最大值查询 nums[i]。- bit1维护 dp[j][1] 的后缀最大值查询 nums[i]通过反向索引实现。滑动窗口处理 i 时先把 i - k 位置的 DP 值插入树状数组保证只用到距离 k 的状态。时间复杂度O(n log M)空间复杂度O(M)M 为值域大小离散化后 M n。Java 实现树状数组 离散化javaimport java.util.*;class Solution {public long maxAlternatingSum(int[] nums, int k) {int n nums.length;// 离散化int[] sorted nums.clone();Arrays.sort(sorted);int m 0;for (int i 0; i sorted.length; i) {if (i 0 || sorted[i] ! sorted[i - 1]) {sorted[m] sorted[i];}}// 映射值到排名 [1, m]MapInteger, Integer rank new HashMap();for (int i 0; i m; i) {rank.put(sorted[i], i 1);}// 树状数组维护前缀最大值Fenwick bit0 new Fenwick(m); // 维护 dp[j][0]查询 nums[i]Fenwick bit1 new Fenwick(m); // 维护 dp[j][1]查询 nums[i]反向索引long[][] dp new long[n][2];long ans 0;for (int i 0; i n; i) {int idx rank.get(nums[i]);// 先查询再插入保证 j i - kif (i k) {// dp[i][1]峰需要前驱是谷且 nums[j] nums[i]long best0 bit0.query(idx - 1); // 查询值 nums[i] 的最大 dp[j][0]dp[i][1] Math.max(nums[i], best0 nums[i]);// dp[i][0]谷需要前驱是峰且 nums[j] nums[i]long best1 bit1.query(m - idx); // 查询值 nums[i] 的最大 dp[j][1]反向索引dp[i][0] Math.max(nums[i], best1 nums[i]);} else {dp[i][0] nums[i];dp[i][1] nums[i];}ans Math.max(ans, Math.max(dp[i][0], dp[i][1]));// 把 i - k 1 位置的值插入树状数组供后续 i 使用if (i - k 1 0) {int insertIdx rank.get(nums[i - k 1]);bit0.update(insertIdx, dp[i - k 1][0]);bit1.update(m - insertIdx 1, dp[i - k 1][1]);}}return ans;}// 树状数组维护前缀最大值class Fenwick {int n;long[] tree;Fenwick(int n) {this.n n;this.tree new long[n 1];}// 在 index 位置更新最大值void update(int index, long val) {while (index n) {tree[index] Math.max(tree[index], val);index index -index;}}// 查询 [1, index] 的最大值long query(int index) {long res 0;while (index 0) {res Math.max(res, tree[index]);index - index -index;}return res;}}}关键点说明1. 离散化nums[i] 范围 1e5离散化后树状数组大小降为 O(n)。2. 反向索引bit1 用 m - idx 1 做索引把值大于 nums[i]的后缀查询转化为前缀查询。3. 滑动插入i - k 1 位置在遍历到 i 时才插入确保任何查询到的 j 都满足 j i - k。4. 初始状态每个元素本身可以单独成子序列所以 dp[i][0/1] 至少为 nums[i]。5. 与 0 取 maxquery 返回 0 表示不从任何前驱转移即子序列只含当前元素已经通过 Math.max(nums[i], best nums[i]) 处理。