千问 LeetCode 3915. 距离至少为 K 的交替子序列的最大和 Python3实现

这道题是 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)

Python 实现

class FenwickTree:
def __init__(self, size):
self.n = size
self.INF = -10**18
self.tree = [self.INF] * (self.n + 2)

def update(self, idx: int, val: int):
while idx <= self.n:
if val > self.tree[idx]:
self.tree[idx] = val
idx += idx & -idx

def query(self, idx: int) -> int:
res = self.INF
while idx > 0:
if self.tree[idx] > res:
res = self.tree[idx]
idx -= idx & -idx
return res

class Solution:
def maxAlternatingSum(self, nums: list[int], k: int) -> int:
n = len(nums)

# 1. 值域离散化
unique_nums = sorted(set(nums))
rank = {v: i + 1 for i, v in enumerate(unique_nums)} # 1-based
m = len(unique_nums)

INF = -10**18

# 2. 两棵树状数组
# bit_down：维护 down 值，用于查询"值小于当前值"的最大 down
# bit_up_rev：维护 up 值（倒序坐标），用于查询"值大于当前值"的最大 up
bit_down = FenwickTree(m)
bit_up_rev = FenwickTree(m)

up = [0] * n
down = [0] * n
max_ans = 0

for i in range(n):
# 3. 延迟激活：把 i-k 位置的状态加入树状数组
if i - k >= 0:
prev = i - k
r = rank[nums[prev]]
bit_down.update(r, down[prev])
bit_up_rev.update(m - r + 1, up[prev]) # 倒序映射，后缀变前缀

cur_r = rank[nums[i]]

# 4. 状态转移
# up[i]：前一个值 < nums[i]，从 bit_down 查询值域 [1, cur_r-1] 的最大 down
best_down = bit_down.query(cur_r - 1)
up[i] = nums[i] + (best_down if best_down != INF else 0)

# down[i]：前一个值 > nums[i]，从 bit_up_rev 查询值域 [cur_r+1, m] 的最大 up
best_up = bit_up_rev.query(m - cur_r)
down[i] = nums[i] + (best_up if best_up != INF else 0)

max_ans = max(max_ans, up[i], down[i])

return max_ans

关键点解析

- 值域离散化：nums[i] 最大 10⁵，但实际不同值最多 n 个，离散化后压缩到 [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"这类题的通用模板整理出来吗？