---

1425. 带限制的子序列和

• 标签：数组、动态规划、队列、滑动窗口、单调队列、堆（优先队列）
• 难度：困难

题目链接

• 1425. 带限制的子序列和 - 力扣

题目大意

描述：给定一个整数数组 $nums$ 和一个整数 $k$。

要求：返回非空子序列的最大和，要求子序列中任意两个相邻元素在原数组中的下标差不超过 $k$。

说明：

• $1 \le k \le nums.length \le 10^5$。
• $-10^4 \le nums[i] \le 10^4$。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：DP + 单调队列

1. 核心思想

定义 $dp[i]$ 表示以 $nums[i]$ 为结尾的满足条件的子序列的最大和。转移时，可以从 $[i-k, i-1]$ 范围内的 $dp[j]$ 转移过来，因为 $i - j \le k$ 保证了相邻元素下标差不超过 $k$。

$$dp[i] = nums[i] + \max(0, \max_{j=i-k}^{i-1} dp[j])$$

计算 $dp[i]$ 时需要一个滑动窗口 $[i-k, i-1]$ 内的 $dp$ 最大值。这是经典的滑动窗口最大值问题，用单调队列优化。

2. 具体步骤

第 1 步：初始化 $dp[0] = nums[0]$，单调队列存储索引，队列中索引对应的 $dp$ 值递减。

第 2 步：遍历 $i = 1 \to n-1$：

• 从单调队列中获取窗口内 $dp$ 最大值的索引 $best$。
• $dp[i] = nums[i] + \max(0, dp[best])$。
• 将 $i$ 加入单调队列（保持递减）。
• 移除窗口外的索引（$< i - k + 1$）。

第 3 步：返回 $\max(dp)$。

3. 举例说明

以 $nums = [10, -2, -10, -5, 20], k = 2$ 为例：

• $dp[0] = 10$，队列：$[0]$（$dp[0]=10$）
• $i=1$：窗口 $[0,0]$，$best=0$，$dp[1] = -2 + 10 = 8$，队列：$[0,1]$
• $i=2$：窗口 $[0,1]$，$best=0$，$dp[2] = -10 + 10 = 0$，队列：$[0,1,2]$
• $i=3$：窗口 $[1,2]$，$best=1$（$dp[1]=8$），$dp[3] = -5 + 8 = 3$，队列：$[1,3]$
• $i=4$：窗口 $[2,3]$，$best=3$（$dp[3]=3$），$dp[4] = 20 + 3 = 23$，队列：$[4]$

结果：$\max(10, 8, 0, 3, 23) = 23$。

思路 1：代码

from collections import deque

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        # 单调递减队列（存索引），队头是窗口内 dp 最大值
        dq = deque([0])

        for i in range(1, n):
            # 取窗口内最大 dp
            best = dq[0]
            dp[i] = nums[i] + max(0, dp[best])

            # 维护单调队列
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            dq.append(i)

            # 移除窗口外的元素
            if dq[0] <= i - k:
                dq.popleft()

        return max(dp)

思路 1：复杂度分析

• 时间复杂度：$O(n)$，每个元素入队出队各一次。
• 空间复杂度：$O(n)$，DP 数组和单调队列。