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``。 自建示例 -------- 可以跳过负数但必须满足下标距离限制: .. code-block:: text 输入:nums = [10,-5,-2,20], k = 2 输出:28 解释:选择下标 0、2、3,元素和为 10 - 2 + 20 = 28,相邻下标差分别为 2 和 1。 全部元素为负时选择最大的单个元素: .. code-block:: text 输入:nums = [-3,-1], k = 1 输出:-1 解释:子序列必须非空,选择 -1 最优。