LeetCode 题解工作台
带限制的子序列和
给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i 且 j - i 。 数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字）…
6
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示以 结尾的满足条件的子序列的最大和。初始时 $f[i] = 0$，答案为 $\max_{0 \leq i \lt n} f(i)$。 我们注意到题目需要我们维护滑动窗口的最大值，这就是一个典型的单调队列应用场景。我们可以使用单调队列来优化动态规划的转移。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 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
解题思路
方法一：动态规划 + 单调队列
我们定义 表示以 结尾的满足条件的子序列的最大和。初始时 ，答案为 。
我们注意到题目需要我们维护滑动窗口的最大值，这就是一个典型的单调队列应用场景。我们可以使用单调队列来优化动态规划的转移。
我们维护一个从队首到队尾单调递减的单调队列 ，队列中存储的是下标 ，初始时，我们将一个哨兵 加入队列中。
我们遍历 从 到 ，对于每个 ，我们执行以下操作：
- 如果队首元素 满足 ，说明队首元素已经不在滑动窗口内，我们需要从队首弹出队首元素；
- 然后，我们计算 ，表示我们将 加入滑动窗口后的最大子序列和；
- 接下来，我们更新答案 ；
- 最后，我们将 加入队列尾部，并且保持队列的单调性，即如果 ，我们需要将队尾元素弹出，直到队列为空或者 。
最终答案即为 。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
q = deque([0])
n = len(nums)
f = [0] * n
ans = -inf
for i, x in enumerate(nums):
while i - q[0] > k:
q.popleft()
f[i] = max(0, f[q[0]]) + x
ans = max(ans, f[i])
while q and f[q[-1]] <= f[i]:
q.pop()
q.append(i)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates knowledge of dynamic programming with optimizations for sliding windows and heaps.
- question_mark
The candidate discusses the importance of efficient state transitions and boundary conditions in dynamic programming.
- question_mark
The candidate understands the trade-offs of using a heap for maintaining the maximum sum of subsequences in the context of a sliding window.
常见陷阱
外企场景- error
Ignoring the need to maintain a sliding window of maximum subsequence sums, leading to inefficient solutions.
- error
Overcomplicating the solution by using brute-force methods without taking advantage of dynamic programming and heap optimizations.
- error
Failing to correctly handle edge cases like negative numbers or very small arrays, which can impact the correctness of the dynamic programming solution.
进阶变体
外企场景- arrow_right_alt
Allowing for an additional constraint where the sum of subsequence elements must be greater than a given threshold.
- arrow_right_alt
Modifying the problem to include more complex constraints on subsequence selection, such as allowing at most two elements to be skipped.
- arrow_right_alt
Changing the problem to find the minimum sum instead of the maximum sum, which would require reversing the optimization direction.