千问 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这类题的通用模板整理出来吗

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

相关推荐

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

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

Docker Compose 部署 MySQL：从原理到实战的容器化数据库解决方案

更多资讯

Windows 10便携版部署避坑：路径权限、配置固定与版本回滚

MATLAB细菌菌落自动计数：鲁棒预处理与可解释图像分析流水线

Python抢票脚本全解析：登录态维护、并发轮询与订单提交实战

云服务器Nvidia驱动安装完全指南：从环境检查到排错

WPF富文本编辑器：三层架构、格式同步与docx导出

给 Claude Code 装 Matt Pocock 技能包，五个坑我替你踩完了：符号链接、managed 标识、路径权限全排雷

今日更新

Verilog实现FPGA密码锁：矩阵键盘与状态机设计实战

数据服务监控运维实战：从指标体系到告警治理与故障排查

FreeRTOS任务通知实战详解：内核原理、API与避坑指南

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？