调试中...
困难
相关标签
相关企业
提示
给你一个整数数组 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
通过次数
8.9K
提交次数
18.1K
通过率
49.2%
相关企业
提示 1
Use dynamic programming.
提示 2
Let dp[i] be the solution for the prefix of the array that ends at index i, if the element at index i is in the subsequence.
提示 3
dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], ..., dp[i-1])
提示 4
Use a heap with the sliding window technique to optimize the dp.
相似题目
评论 (0)
贡献者
© 2025 领扣网络（上海）有限公司
1 人在线
行 1，列 1