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

这道题是 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)Python 实现class FenwickTree:def __init__(self, size):self.n sizeself.INF -10**18self.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] validx idx -idxdef query(self, idx: int) - int:res self.INFwhile idx 0:if self.tree[idx] res:res self.tree[idx]idx - idx -idxreturn resclass 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-basedm len(unique_nums)INF -10**18# 2. 两棵树状数组# bit_down维护 down 值用于查询值小于当前值的最大 down# bit_up_rev维护 up 值倒序坐标用于查询值大于当前值的最大 upbit_down FenwickTree(m)bit_up_rev FenwickTree(m)up [0] * ndown [0] * nmax_ans 0for i in range(n):# 3. 延迟激活把 i-k 位置的状态加入树状数组if i - k 0:prev i - kr 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] 的最大 downbest_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_r1, m] 的最大 upbest_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-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这类题的通用模板整理出来吗