目录

1425:带限制的子序列和(2032 分)

力扣第 186 场周赛第 4 题

题目

给你一个整数数组 nums 和一个整数 k ,请你返回 非空 子序列元素和的最大值,子序列需要满足:子序列中每两个 相邻 的整数 nums[i]nums[j] ,它们在原数组中的下标 ij 满足 i < jj - 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[j] = max(f[j-k:j]+[0])+nums[j]
  • 求滑动窗口的最值,可以用单调队列优化

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [-inf]*n
        Q = deque()
        for j,a in enumerate(nums):
            if Q and Q[0][0]<j-k:
                Q.popleft()
            f[j] = a+Q[0][1] if Q and Q[0][1]>0 else a
            while Q and Q[-1][1]<=f[j]:
                Q.pop()
            Q.append((j,f[j]))
        return max(f)

307 ms