题目来源
题目概述
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步,你最多可以往前跳 k 步,但你不能跳出数组的边界。也就是说,你可以从下标 i 跳到** [i + 1, min(n - 1, i + k)] **包含 两个端点的任意位置。
你的目标是到达数组最后一个位置**(下标为 n - 1 )**,你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
思路分析
可以使用一个数组来记录到达 i 位置时可以取得的最高分数。这个分数就是i - k到i - 1位置的最高分数 + i位置的分数。
代码实现
java实现
public class Solution {
public int maxResult(int[] nums, int k) {
// 记录i位置的最高分数
int[] answer = new int[nums.length];
// 记录向前最多k位的最大分数下标
int maxIndex = 0;
answer[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
// 我们只需要比较 maxIndex 和 新空出来的位置,就能找出新的最大值
maxIndex = answer[maxIndex] > answer[i - 1] ? maxIndex : i - 1;
answer[i] = answer[maxIndex] + nums[i];
// 如果当前的maxIndex被删除,寻找新的maxIndex
if (maxIndex <= i - k) {
maxIndex = i - k + 1;
for (int j = maxIndex + 1; j < i; j++) {
maxIndex = answer[maxIndex] > answer[j] ? maxIndex : j;
}
}
}
return answer[nums.length - 1];
}
}
c++实现
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
// 记录 i 位置的最高分数
vector<int> answer = vector<int>(nums.size());
// 记录可以到达 i 位置的最多前 k 个位置的最高分数
int maxIndex = 0;
answer[0] = nums[0];
for (int i = 1; i < nums.size(); i++) {
// 比较最大值和新空出来的位置
maxIndex = answer[maxIndex] > answer[i - 1] ? maxIndex : i - 1;
answer[i] = answer[maxIndex] + nums[i];
// 如果最大值被删除,寻找新的最大值
if (maxIndex <= i - k) {
maxIndex = i - k + 1;
for (int j = maxIndex + 1; j < i; j++) {
maxIndex = answer[maxIndex] > answer[j] ? maxIndex : j;
}
}
}
return answer[nums.size() - 1];
}
};