Jump Game

Description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

这道题采用贪心算法，计算当前位置能够到达的最远距离，设置为maxDis, 然后遍历数组，当当前位置大于maxDis时，说明此位置是到达不了的，那么无论下面怎么走，都注定到达不了终点，所以可以直接返回false了；反之，如果当maxDis大于等于终点时，说明肯定有一种方法可以到达终点，无需继续下去，此时也可以返回。如果这两个条件都不满足时，比较当前位置所能到达的最大位置与maxDis的大小，更新maxDis的值。

代码如下：

public class Solution {
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    public boolean canJump(int[] A) {
        // write your code here
        int maxDis = 0;
        for(int i = 0; i < A.length; i++){
            if(i > maxDis || maxDis >= A.length-1){
                break;
            }
            maxDis = maxDis > i+A[i] ? maxDis : i+A[i];
        }
        return maxDis >= A.length-1;
    }
}