LeetCode 1425. 带限制的子序列和【动态规划,单调队列优化】2032

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。

示例 1：

输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。

示例 2：

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。

示例 3：

输入：nums = [10,-2,-10,-5,20], k = 2
输出：23
解释：子序列为 [10, -2, -5, 20] 。

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

---

解法 动态规划+单调队列优化

我们用 $f(i)$ 表示在数组的前 $i$ 个数中进行选择，并且恰好选择了第 $i$ 个数，可以得到的最大和。那么 $f(i)$ 的状态转移分为两种：

• 如果我们在前 $i$ 个数中只选择了 $nums[i]$ ，那么和即为；
  $$f[i]=\text{nums}[i]$$
• 如果我们还选择了其它的数，那么我们可以枚举上一个选择的数 $nums[j]$ ，并通过 $f[j]$ 进行状态转移。具体地，根据题目的要求，相邻两个被选择的整数在数组中的下标之差必须小于等于 $k$ ，也就是 $0<i-j\le k$ ，因此可以写出如下的状态转移方程：
  $$f[i]=\underset{\max (i-k,0)\le j<i}{\max }(f[j])+\text{nums}[i]$$

将两种情况写在一起，就可以得到状态转移方程：
$$f[i]=\max \left(\underset{\max (i-k,0)\le j<i}{\max }(f[j]),0\right)+\text{nums}[i]$$
这个状态转移方程看上去很吓人，但我们可以从最简单的方法开始想起。对于每一个 $f(i)$，我们只要枚举与 $i$ 的差值是否小于等于 $k$ 的所有 $j$ ，并在这些 $j$ 中选择一个最大的 $f[j]$ 进行状态转移即可。如果最大的 $f[j]$ 小于 $0$ ，那么我们不进行状态转移，只选择 $nums[i]$ 。

然而这样做的时间复杂度为 $O(nk)$ ，会超出时间限制，因为枚举 $i$ 和 $j$ 的时间复杂度分别为 $O(n)$ 和 $O(k)$ 。那么我们如何进行优化呢？

观察上面的状态转移方程，我们大致有一个这样的想法：对于每一个 $i$，我们选择的都是满足要求的 $j$ 中最大的 $f[j]$ 值。那么如果 $f(i)$ 是从 $f[j]$ 转移而来的，只要 $j$ 与 $i+1$ 相差不超过 $k$ ，$f[i+1]$ 也很有可能从 $f[j]$ 转移而来。

这个想法也就是我们熟知的「单调栈」或者「单调队列」。不妨试着使用它们对状态转移方程进行优化。

单调队列优化

在从小到大枚举 $i$ 的过程中，假设我们有两个位置 $j_1$ 和 $j_2$ 可以考虑进行转移，并且 $j_1<j_2$ 。如果 $f[j_1]\le f[j_2]$​ ，那么我们可以断定，对于以后会枚举到的所有 $i$ ，$j_1$ 都不会优于 $j_2$​ 了。换句话说，我们可以直接「扔掉」$j_1$ ，因为它不会转移到后续的任何状态。

这是为什么呢？我们这样想，对于任意一个满足 $j_1<j_2<i$ 的 $i$ ，如果它从 $j_1$ 转移而来，那么它一定也能从 $j_2$ 转移而来，这是因为转移的唯一要求是 $i$ 和 $j$ 相差不超过 $k$ ，那么在 $i$ 和 $j_1$ 满足要求的前提下，$i$ 和 $j_2$ 也一定满足要求。并且 $f[j_1]\le f[j_2]$ ，那么 $j_2$ 一定不比 $j_1$ 差。那么在「有生之年」，我们在进行转移时就不需要考虑 $j_1$ 了。

因此，我们可以考虑使用一个「单调栈」来维护所有可能会考虑的 $j$ 。为什么它是一个「栈」呢？我们来看看它的具体维护方法：

• 假设我们当前维护了这样的一个「单调栈」，它包含 $j_1,j_2,\cdots ,j_x$ ，并且 $j_1<j_2<\cdots <j_x$ 。根据上面提到的性质，必定有 $f[j_1]>f[j_2]>\cdots >f[j_x]$ 。如果我们需要将一个新的 $j$ 值 $j_y$ 放入单调栈中，那么我们从栈顶元素开始考虑：如果 $f[j_x]\le f[j_y]$ ，那么根据上文的推导，我们可以直接「扔掉」$j_x$ ，也就是将栈顶元素弹出。
• 以此类推，我们可以不断地弹出栈顶元素，直到栈顶元素对应的 $f$ 值大于 $f[j_y]$ 或者栈为空。此时我们再将 $j_y$ 放入栈顶，就得到了一个新的「单调栈」。
• 这样以来，栈底的 $j$ 对应着最大的 $f[j]$ 值，我们用它来转移到 $f(i)$ 就行了。

然而，这样的设计存在两个问题：

• 我们使用的是一个「栈」，在仅使用栈的 API 的前提下，而我们并没有办法获得「栈底」的元素；
• 栈底的 $j$ 可能与当前的 $i$ 值的差大于 $k$ 。

因此，我们需要用「队列」来代替栈，即单调队列。

• 对于第一个问题，我们可以通过获取队首元素解决。
• 对于第二个问题，我们要做的是不断地将队首的元素弹出，直到队首的 $j$ 与当前的 $i$ 值的差小于 $k$ 为止。由于我们需要「取出队首元素」「取出队尾元素」这两种操作，因此我们使用的是「双端队列」。

算法流程——我们使用单调队列进行优化的动态规划的算法流程如下：

1. 我们用一个双端队列来维护所有可能会进行转移的 $j$ 值。在队列中，这些 $j$ 值单调递增，但是它们对应的 $f[j]$ 值是单调递减的；
2. 我们从小到大枚举 $i$ 。在枚举的每一步中，单调队列的队首元素就是最优的转移选择。但由于题目要求相邻的两个数的位置最多间隔 $k$ ，因此我们需要从队首弹出元素，直到队首的 $j$ 值与 $i$ 的差值小于等于 $k$ ；
3. 在计算出 $f(i)$ 后，我们将 $i$ 根据规则放入单调队列的队尾。在放入之前，可能会弹出若干队尾的元素。
4. 最终的答案即为所有 $f(i)$ 中的最大值。

class Solution {
public:int constrainedSubsetSum(vector<int>& nums, int k) {int n = nums.size();// 存储动态规划结果的数组vector<int> f(n);// 我们直接放入f[0]的值，防止处理边界情况f[0] = nums[0];// 单调队列deque<int> q;// 一开始唯一的j为0q.push_back(0);int ans = nums[0];for (int i = 1; i < n; ++i) {// 如果队首的j与i的差值大于k，则不满足要求，弹出while (!q.empty() && i - q.front() > k) q.pop_front();// 此时队首的j即为最优的j值f[i] = max(f[q.front()], 0) + nums[i];ans = max(ans, f[i]);// 维护队列的单调性，不断从队尾弹出元素while (!q.empty() && f[i] >= f[q.back()]) q.pop_back();// 将i作为之后的新j值放入队尾q.push_back(i);}return ans;}
};

复杂度分析：

• 时间复杂度：$O(n)$ ，其中 $n$ 是数组 $\text{nums}$ 的长度。每一个数组下标都被放入队列一次，并且被弹出队列最多一次，因此处理队列的时间总计为 $O(n)$ ，与枚举 $i$ 的时间 $O(n)$ 相加仍然为 $O(n)$ 。
• 空间复杂度：$O(n)$ ，数组 $f$ 和单调队列各需要 $O(n)$ 的空间。