千问 LeetCode 3915. 距离至少为 K 的交替子序列的最大和 Rust实现-北京尧图网络

这道题是 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)Rust 实现use std::cmp::max;use std::collections::BTreeSet;struct FenwickTree {n: usize,tree: Veci64,}impl FenwickTree {fn new(n: usize) - Self {FenwickTree {n,tree: vec![i64::MIN / 2; n 2], // 初始化为极小值}}// 单点取 max 更新fn update(mut self, mut idx: usize, val: i64) {while idx self.n {self.tree[idx] max(self.tree[idx], val);idx idx idx.wrapping_neg(); // idx idx (-idx)}}// 前缀最大值查询 [1, idx]fn query(self, mut idx: usize) - i64 {let mut res i64::MIN / 2;while idx 0 {res max(res, self.tree[idx]);idx - idx idx.wrapping_neg();}res}}impl Solution {pub fn max_alternating_sum(nums: Veci32, k: i32) - i64 {let n nums.len();let k k as usize;// 1. 值域离散化let mut sorted: Veci32 nums.clone();sorted.sort();sorted.dedup();let m sorted.len();// 2. 两棵树状数组// bit_down维护 down 值用于查询值小于当前值的最大 down// bit_up_rev维护 up 值倒序坐标用于查询值大于当前值的最大 uplet mut bit_down FenwickTree::new(m);let mut bit_up_rev FenwickTree::new(m);let mut up vec![0i64; n];let mut down vec![0i64; n];let mut ans 0i64;for i in 0..n {// 3. 延迟激活把 i-k 位置的状态加入树状数组if i k {let prev i - k;let prev_rank sorted.binary_search(nums[prev]).unwrap() 1; // 1-basedbit_down.update(prev_rank, down[prev]);bit_up_rev.update(m - prev_rank 1, up[prev]); // 倒序映射后缀变前缀}let cur_rank sorted.binary_search(nums[i]).unwrap() 1; // 1-based// 4. 状态转移// up[i]前一个值 nums[i]从 bit_down 查询值域 [1, cur_rank-1] 的最大 downlet best_down bit_down.query(cur_rank - 1);up[i] nums[i] as i64 if best_down i64::MIN / 2 { 0 } else { best_down };// down[i]前一个值 nums[i]从 bit_up_rev 查询值域 [cur_rank1, m] 的最大 uplet best_up bit_up_rev.query(m - cur_rank);down[i] nums[i] as i64 if best_up i64::MIN / 2 { 0 } else { best_up };ans max(ans, max(up[i], down[i]));}ans}}关键点解析- 值域离散化nums[i] 最大 10⁵但实际不同值最多 n 个离散化后压缩到 [1, m]树状数组大小可控- 延迟激活这是处理下标距离 ≥ k的关键技巧——遍历时不立即把当前状态加入树状数组而是等 k 步后再加入这样查询时自然只看到距离 ≥ k 的前驱状态- 后缀查询技巧树状数组天然支持前缀查询要查值大于当前值的最大值把排名 r 反转为 m - r 1就把后缀查询变成了前缀查询- Rust 特有注意点idx (-idx) 在 Rust 中需要用 idx idx.wrapping_neg() 来避免无符号整数的取负溢出问题树状数组初始值设为 i64::MIN / 2 防止加法溢出- 时间复杂度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 的交替子序列的最大和 Rust实现

相关推荐

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

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

VMware macOS虚拟机磁盘空间优化：从原理到实践的完整瘦身指南

更多资讯

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 成本测算与选型避坑（附配置）

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