labuladong讲解

你好，同学。欢迎来到 NOI 提高组算法专题强化训练。

今天我们要攻克的是 “动态规划 + 单调队列优化” 的高阶实战题目：带限制的子序列和。这道题是单调队列优化 DP 的教科书级案例，也是从 $O(N \cdot K)$ 降维打击到 $O(N)$ 的经典范式。

---

一、 预备知识点

在挑战本题前，请确保你已经熟练掌握：

1. 动态规划（DP）：理解状态转移方程的构建。
2. 单调队列（Monotonic Queue）：如何在 $O(1)$ 时间内维护并查询滑动窗口内的最值。
3. 子序列定义：子序列不要求连续，但本题对子序列中相邻元素的原始下标距离做了限制。

---

二、 NOI 竞赛题目描述

题目名称：带限制的子序列和 (Constrained Subsequence Sum) 时间限制：1.0s 内存限制：256MB

【问题描述】 给你一个整数数组 $nums$ 和一个整数 $k$。请你找出 $nums$ 的一个 非空 子序列，使得该子序列中任意两个相邻元素在原数组中的下标 $i$ 和 $j$（满足 $i < j$）满足条件：$j - i \le k$。 请你返回这个子序列的最大和。

【输入格式】 第一行包含两个整数 $n$ 和 $k$。 第二行包含 $n$ 个整数，表示数组 $nums$ 的元素。

【输出格式】 输出一个整数，表示满足条件的最大子序列和。

【样例 1】

• 输入：

  5 2
  10 2 -10 5 20
  

• 输出：37
• 解释：子序列为 [10, 2, 5, 20]，下标为 0, 1, 3, 4。

【样例 2】

• 输入：

  3 1
  -1 -2 -3
  

• 输出：-1
• 解释：非空子序列，必须选一个，选最大的 -1。

【样例 3】

• 输入：

  5 2
  10 -2 -10 -5 20
  

• 输出：23
• 解释：子序列为 [10, -2, -5, 20]。

【数据规模与约定】

• $1 \le k \le n \le 10^5$
• $-10^4 \le nums[i] \le 10^4$

---

三、 启发式思路引导：草稿纸上的推演

请拿出草稿纸，随我一起进行逻辑建模：

1. 定义状态

设 $dp(i)$ 为：以 $nums(i)$ 结尾的满足条件的子序列最大和。

2. 状态转移方程

为了让以 $nums(i)$ 结尾的子序列和最大，我们需要在它前面的合法范围内（即下标在 $(i-k)$ 到 $(i-1)$ 之间）找到一个最大的 $dp(j)$。

• 如果前面最大的 $dp(j)$ 是正数，那么 $dp(i) = nums(i) + dp(j)$。
• 如果前面最大的 $dp(j)$ 是负数，那我们还不如只选当前的 $nums(i)$ 自己。
• 转移方程：$dp(i) = nums(i) + \max(0, \max(dp(j))) \quad \text{其中 } i-k \le j < i$。

3. 寻找性能瓶颈

如果暴力枚举 $j$，复杂度是 $O(n \cdot k)$。在 $n=10^5, k=10^5$ 的极限数据下，计算量可达 $10^{10}$，必然超时。

• 观察：我们在一个大小为 $k$ 的滑动窗口内寻找最大值。
• 结论：使用单调队列优化，将查询最大值的时间降为 $O(1)$。

---

四、 复杂度分析与时间复杂度优化建议

• 时间复杂度：$O(n)$。 每个下标入队一次、出队一次。单调队列维护了窗口内的 $dp$ 极大值。
• 空间复杂度：$O(n)$。 需要一个 $dp$ 数组和一个存储下标的单调队列。

优化建议：

1. 哨兵思想：结果 $ans$ 初始值应设为 $nums(0)$ 或极小值。
2. deque 效率：在 NOI 竞赛中，如果数据量极大，std::deque 性能不如手动模拟数组队列：int q(MAXN), head=0, tail=0;。

---

五、 算法流程图（伪代码逻辑）

为了避开特殊符号导致 Mermaid 渲染错误，我们使用文字逻辑描述：

graph TD
    Start(开始处理任务) --> Init(初始化 dp 数组, 单调队列 dq)
    Init --> Loop(遍历下标 i 从 0 到 n 减 1)
    Loop -- 结束 --> EndResult(输出全局 ans)
    
    Loop -- 正在处理 i --> PopExpired(若队首下标小于 i 减 k 则从队首弹出)
    PopExpired --> CalcDP(当前 dp 等于 nums_i 加 队首对应的正数dp值)
    CalcDP --> UpdateAns(更新全局最大值 ans)
    
    UpdateAns --> MaintainMono(循环弹出队尾直到队尾 dp 大于等于当前 dp)
    MaintainMono --> PushIdx(将下标 i 压入队尾)
    PushIdx --> Loop

---

六、 题解标准代码提示（C++14 标准）

在编写代码时，请注意以下竞赛细节：

// 关键逻辑提示（非完整运行代码）
// 1. 使用 deque<int> dq 维护单调递减的 dp 下标
// 2. 对于每个 i:
//    while (!dq.empty() && dq.front() < i - k) dq.pop_front();
//    dp[i] = nums[i] + (dq.empty() ? 0 : max(0, dp[dq.front()]));
//    while (!dq.empty() && dp[i] >= dp[dq.back()]) dq.pop_back();
//    dq.push_back(i);

---

七、 读题关键词总结

在 NOI 提高组读题时，看到以下组合要立刻反应：

1. “最大子序列和” $\rightarrow$ 动态规划 DP。
2. “相邻元素间距 $\le K$” $\rightarrow$ 状态转移受到滑动窗口限制。
3. “$N, K \le 10^5$” $\rightarrow$ 强制要求 $O(N)$ 算法，排除 $O(NK)$ 暴力和 $O(N \log N)$ 优先队列。

教练寄语： 单调队列优化 DP 是从“业余选手”迈向“专业选手”的一道坎。它的精髓在于**“剔除老旧且无能的决策点”**。当你能在草稿纸上顺畅地模拟出队列的弹出和压入过程时，你就已经掌握了它的灵魂。加油！