题目详情
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步,你最多可以往前跳 k 步,但你不能跳出数组的边界。也就是说,你可以从下标 i 跳到 [i + 1, min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置(下标为 n - 1 ),你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
示例 1:
输入:
nums = [1,-1,-2,4,-7,3], k = 2
输出:
7
解释:你可以选择子序列 [1,-1,4,3] (上面加粗的数字),和为 7 。
示例 2:
输入:
nums = [10,-5,-2,4,0,3], k = 3
输出:
17
解释:你可以选择子序列 [10,4,3] (上面加粗数字),和为 17 。
示例 3:
输入:
nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
输出:
0
提示:
1 <= nums.length, k <= 105
-104 <= nums[i] <= 104
朴素算法代码
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
int n=nums.size();
int f[n+1];//f[j]是目的地是j的所有跳法的集合 属性是跳法的最大得分
memset(f,-0x3f,sizeof(f));
f[0]=nums[0];
for(int j=1;j<=n-1;j++){
for(int s=1;s<=k;s++){
if(j-s>=0){
f[j]=max(f[j],f[j-s]+nums[j]);
}
}
}
return f[n-1];
}
};
使用双端队列优化的算法
朴素算法每次循环都要比较f[j-k,j-1]k种情况,取最大值
这是不是很像滑动窗口?
利用154.滑动窗口的双端队列可以省去一维获取最大值的时间
详情Link
优化代码
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
int n=nums.size();
int f[n+1];//f[j]是目的地是j的所有跳法的集合 属性是跳法的最大得分
memset(f,-0x3f,sizeof(f));
f[0]=nums[0];
int q[n+1];
memset(q,0,sizeof(q));
q[0]=0;
int front=0,rear=1;
for(int j=1;j<=n-1;j++){
f[j]=f[q[front]]+nums[j];
if(j>=k&&q[front]<j-k+1) front++;
while(rear!=front&&f[j]>=f[q[rear-1]]) rear--;
q[rear++]=j;
}
return f[n-1];
}
};