1425. Constrained Subsequence Sum¶
题目信息¶
- 题号:
1425
- 难度:
Hard
- 主题:
动态规划、单调队列、子序列
- 原题:
- 重点:
选择非空子序列,相邻被选下标之差不能超过
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 最优。