带限制的子序列和

难度: Hard

给你一个整数数组 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

Submission

运行时间: 260 ms

内存: 27.7 MB

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.append(0)
        stk = deque([-1])
        maxVal = -inf
        for i in range(n):
            if stk[0] < i - k:
                stk.popleft()

            if nums[stk[0]] > 0:
                nums[i] += nums[stk[0]]
            if nums[i] > maxVal:
                maxVal = nums[i]
            
            while stk and nums[stk[-1]] < nums[i]:
                stk.pop()
            stk.append(i)
        return maxVal

Explain

这个题解使用了动态规划加单调队列的优化方法。动态规划数组`nums`的每个元素`nums[i]`被更新为以`nums[i]`结尾的最大子序列和。考虑到每个元素只能与前面距离不超过`k`的元素组成子序列，所以每次计算`nums[i]`时，只需要考虑`nums[i-k]`到`nums[i-1]`这个区间内的最大值。为了高效地获取这个区间内的最大值，使用了单调队列`stk`，这个队列存储的是索引，并且保证队列中的元素对应的`nums`值是单调递减的。对于每个新的`i`, 我们从队头移除超过距离限制的索引，然后将`nums[i]`与队头所指元素的`nums`值相加（如果这个值是正的），这样`nums[i]`就成了以`i`为结尾的最大子序列和。然后我们将当前的`i`添加到队列中，同时保持队列的单调性。这样，队列的头总是当前窗口的最大值。最终，遍历完成后的最大`nums`值即为答案。

时间复杂度: O(n)

空间复杂度: O(k)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.append(0) # 添加哨兵元素，简化边界处理
        stk = deque([-1]) # 单调队列初始化，存储索引，-1作为初始最大和的哨兵
        maxVal = -inf # 初始化最大值为负无穷
        for i in range(n):
            if stk[0] < i - k:
                stk.popleft() # 移除超出范围k的元素索引

            if nums[stk[0]] > 0:
                nums[i] += nums[stk[0]] # 将当前值加上队列中最大值（若为正）
            if nums[i] > maxVal:
                maxVal = nums[i] # 更新全局最大值
            
            while stk and nums[stk[-1]] < nums[i]:
                stk.pop() # 维护队列的单调递减性
            stk.append(i) # 将当前索引加入队列
        return maxVal # 返回最大子序列和

Explore

单调队列相比于堆（优先队列）在这个应用场景中有更高的效率。单调队列能够以O(1)的时间复杂度实现获取最大值，同时添加和删除操作平均也能达到O(1)的时间复杂度。而堆的插入和删除操作时间复杂度为O(log k)，在这里k为子序列的长度限制。特别是在需要频繁移除特定位置元素（如超出滑动窗口范围的元素）时，单调队列能够直接从队列头部快速移除，而堆则需要进行更复杂的操作来维护堆的性质。因此，在需要频繁更新区间最大值的场景中，使用单调队列是更优的选择。

确实如此，如果队头元素的`nums`值为负或零，则不进行加法操作。逻辑依据在于我们在寻找以`nums[i]`结尾的最大子序列和时，若前面的最大和为负或零，那么加上这个值不会使`nums[i]`增大，反而可能变小。因此，在这种情况下，选择不加入任何前面的子序列和（即使`nums[i]`单独作为一个子序列），是为了确保不减少`nums[i]`的值，从而有助于求得最大子序列和。

在单调队列的实现中，每次处理一个新的元素`nums[i]`时，会首先检查队列头部的索引是否已经超出了当前元素索引`i`与最大距离`k`的范围。即检查队头的索引是否小于`i - k`。由于队列是按照索引顺序从小到大排列的，当队头的索引小于`i - k`时，表示这个索引已经不在允许的距离范围内，因此可以安全地将其移除。这个过程是在每次迭代时进行的，确保了只有当前距离范围内的索引被保留在队列中，从而保证了算法的正确性。