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

def solution(n,nums):
    if not n: return -1
    maxL = nums[0]
    dp = [nums[i] for i in range(n)] #以nums[i]为结尾的序列所能获得的maxVal
    for i in range(1,n):
        #1)从nums[0:i)不能到达第i个位置，即当前所能到达的 maxL < i，则无法跳到终点。
        #2)maxL >= i, 则从nums[0:i)某个位置一定能跳到位置i
        if maxL < i: return -1
        maxL = max(maxL, i+nums[i])#更新maxL
        #往回寻找能跳到位置i的最大值位置
        j = i-1 
        #目标位置就是距离位置 i 最近且能到达位置 i 的位置！！
        #假设有且只有k,j都能到达 i，且 k < j < i。则最优解只可能是由k跳到j,再由j跳到i。因为nums值都>=0。
        while(nums[j] + j < i): j -= 1
        #更新以位置i为结尾的序列的maxVal
        dp[i] = max(dp[i],nums[i]+dp[j])
    return dp[-1]

if __name__ == "__main__":
    n = int(input())
    data = list(map(int,input().split()))
    res = solution(n,data)
    print(res)