千问 LeetCode 3915. 距离至少为 K 的交替子序列的最大和 TypeScript实现
这道题是 LeetCode 3915「距离至少为 K 的交替子序列的最大和」，核心思路是 DP + 值域离散化 + 树状数组（Fenwick Tree）优化，将复杂度从 O(n²) 降到 O(n log n)。
题目理解
给定数组 nums 和整数 k，选一个下标严格递增的子序列，满足：
1. 相邻选中下标之差 ≥ k
2. 选出的值严格交替（小大 或 大小 波动，不能相等）
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 位置的状态加入树状数组，保证下标距离 ≥ k
4. 树状数组优化：用两棵树状数组分别维护"值小于当前值"和"值大于当前值"的最大 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 Map<number, number>();
sorted.forEach((v, i) => rankMap.set(v, i + 1)); // 1-based
const m = sorted.length;
// 2. 两棵树状数组
// bitDown：维护 down 值，用于查询"值小于当前值"的最大 down
// bitUpRev：维护 up 值（倒序坐标），用于查询"值大于当前值"的最大 up
const 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] 的最大 down
const bestDown = bitDown.query(curRank - 1);
up[i] = nums[i] + (bestDown <= INF ? 0 : bestDown);
// down[i]：前一个值 > nums[i]，从 bitUpRev 查询值域 [curRank+1, m] 的最大 up
const 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-0=2≥k，5>2 严格交替，得分 7 ✅
- nums = [3,5,4,2,4], k = 1：选下标 [0,1,3,4]，值 [3,5,2,4]，3<5>2<4 严格交替，得分 14 ✅
- nums = [5], k = 1：长度为 1 始终有效，得分 5 ✅
这道题的难点在于延迟激活 + 树状数组优化区间最值的组合，需要我帮你把"树状数组优化 DP"这类题的通用模板整理出来吗？