题意

给定一个数组，每个值表示当前位置能向后移动的最远距离，同时也表示得分。

求从数组开始跳到数组结束的最大得分

限制：

数组长度不大于10000

方法

枚举遍历

使用一个辅助数组，记录每个位置能得到的最大得分。

遍历原数组，对于每个可行位置，更新这个位置之后的最大得分的值。

最终输出重终点的值即可。

以题目样例[2,4,2,1,0,100]为例

最后输出 106即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int maxJumpGrade(vector<int>& nums) {
        if(nums.size() == 0)return -1; // 特殊情况处理
        vector<int> res(nums.size(), -1);
        res[0] = nums[0]; // 初始化
        for (int i = 0; i < nums.size(); i++) {
          if (res[i] == -1) // 不可达
            continue;
          for (int j = 1; j <= nums[i]; j++) { // 枚举之后的位置
            if (i + j >= nums.size())  // 超过范围
              break;
            res[i + j] = max(res[i + j], res[i] + nums[i + j]); // 更新后面的最大值
          }
        }
        return res[nums.size() - 1];
    }
};

复杂度分析

时间复杂度: 对于每个位置，最坏情况更新范围是数组长度，所以时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 主要消耗在辅助数组，所以空间复杂度为$O(n)O(n)$

基于数学性质的性能优化

首先数组的值非负，如果数组中所有值都非0，那么显然每次走一步，可以把整个数组的值都记入加和里，这样的值一定是最大的。

考虑有零的情况，实际上数组可以看做一段非零一段是零一段非零的间隔

对于XXXX0000yyyy

如果要能从x跳到y的任意位置，那么也一定能跳到y的起始位置。

所以要找的是，在0000之前，最后一个能跳到yyyy起始的位置

但是，注意到可能存在xxx000yyy000zzz，其中x能跳到z，而y无法跳到z的情况

所以考虑，维护一个{得分,最远坐标}的大根堆，这样每次检查是否在堆顶元素的范围内，如果在才更新，不在则踢出堆顶。这样，每次堆顶都是可达的最大值。

最后同样输出结果即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int maxJumpGrade(vector<int>& nums) {
        if(nums.size() == 0)return -1; // 特殊情况处理
        vector<int> res(nums.size(), -1);
        // 大根堆，（值，位置），值不包含当前位置
        priority_queue<pair<int,int> > vp;  // value pos
        vp.push({0,0}); // 初始化
        for (int i = 0; i < nums.size(); i++) {
            while(vp.size() && vp.top().second < i){ // 更小的坐标不合法
                vp.pop();
            }
            if(!vp.size()) // 不可达
                continue;
            res[i] = vp.top().first + nums[i];
            if(!nums[i]) // 跳跃距离为0 不会更新后续坐标
                continue;
            vp.push({res[i],min((int)nums.size()-1,i+nums[i])}); // 控制坐标范围
        }
        return res[nums.size() - 1];
    }
};

复杂度分析

时间复杂度: 因为通过堆来维护，相当于堆上排序操作,所以总时间复杂度为$O(n)O(n)$

空间复杂度: 主要两部分，一个是大根堆，一个是结果数组，所以空间复杂度为$O(n)O(n)$