总览

给定数组a和当前位置的索引i，重复以下操作，直到到达最后一个元素。

考虑所有候选“跳转到元素” a[i+1]来a[a[i] + i]。对于索引处的每个此类元素e，请计算v= a[e]+
e。如果元素之一是最后一个元素，请跳到最后一个元素。否则，请跳至带有最大值的元素v。

更简单地说，在触及范围内的元素中，寻找一个可以使您在 下一
跳上走得最远的元素。我们知道此选择x正确，因为与y您可以跳转到的其他每个元素相比，从y可以到达的元素是从可以到达的元素的子集x（除了向后跳转的元素，这显然是错误的选择）。

该算法在O（n）中运行，因为每个元素仅需要考虑一次（可以跳过第二次考虑的元素）。

例

考虑值a，索引i以及index和value之和的数组v。

i ->  0   1   2   3   4   5   6   7   8   9  10  11  12
a -> [4, 11,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1]
v ->  4  12   3   4   5   6   7   8   9  10  11  12  13

从索引0开始并考虑接下来的4个元素。找到最大的一个v。该元素位于索引1，因此跳至1。现在考虑接下来的11个元素。目标触手可及，所以跳到目标。

演示版

参见此处或此处的代码。