1425. Constrained Subsequence Sum

题目信息

题号:

1425

难度:

Hard

主题:

动态规划、单调队列、子序列

原题:

LeetCode 1425

重点:

选择非空子序列,相邻被选下标之差不能超过 k;最大化元素和

题目重述

给定整数数组 nums 和整数 k。选择一个保持原下标顺序的非空子序列,并要求任意相邻两个被选元素的下标差不超过 k。

请返回所有合法子序列中的最大元素和。

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

自建示例

可以跳过负数但必须满足下标距离限制:

输入:nums = [10,-5,-2,20], k = 2
输出:28
解释:选择下标 0、2、3,元素和为 10 - 2 + 20 = 28,相邻下标差分别为 2 和 1。

全部元素为负时选择最大的单个元素:

输入:nums = [-3,-1], k = 1
输出:-1
解释:子序列必须非空,选择 -1 最优。