题解 | #跳跃游戏(二)#

1. 如果最大分数存在，最后一个数一定在里面
2. 初始化pos为n-1，不断向前遍历，看遍历到的位置i能否跳到pos，能说明从 i 最终可以跳到最后。如果i遍历过了0，而pos还未更新到0，说明数组不能跳到最后。
3. 举个例子：

[1,2,3,0,0,1,4]，n=7。初始pos = 6 -> i=5，nums[5]=1可以跳到pos位置，更新位置pos=5，1加入分数中 -> i=4，不能动 -> i=3，不能动 -> i=2，nums[2]=3可以跳到pos=5，更新位置pos=2，3加入分数中 -> i=1, nums[1]=2可以跳到pos=2，更新pos=1，2加入分数中 -> i=0， nums[0]=1，可以跳到pos位置更新pos=0，1加入分数中。

所以最后的分数=4+1+3+2+1 = 11

而数组变成[1,2,2,0,0,1,4]，就挑不到最后，在上面红色字体部分就不会更新pos了，之后前面的元素都到不到pos=5的位置，最后也不存在最大分数

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int nums[N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    int pos = n-1;
    // 若存在最大分数（能走到最后），最后一个元素一定在里面
    int maxS = nums[n-1];
    for(int i = n-2; i>=0; i--){
        // 依次查看前面的元素能否跳到pos位置，能跳到就能跳到最后，并将这些能跳到的加入到分数中，更新位置pos
        if(nums[i]+i>=pos){  
            maxS += nums[i];
            pos = i;
        }
    }
    //如果pos未更新到0，说明从前面挑不到最后
    if(pos!=0)
        printf("-1");
    else
        printf("%d",maxS);
    return 0;

}
// 64 位输出请用 printf("%lld")