55 Jump Game (medium)

• 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.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

SOLUTION

1. 需要一个maxReach记录遍历到当前数为止，最远可以到达的index
2. 遍历整个数组，对于每个entry都更新maxReach，必须保证current Index <= maxReach。如果maxReach >= nums.length - 1，则可以到达末尾。如果中途不满足current Index <= maxReach，则退出循环，无法到达。

class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return true;
        
        int maxReach = 0;
        
        for (int i = 0; i < nums.length && i <= maxReach; i++) {
            maxReach = Math.max (maxReach, nums[i] + i);
            
            if (maxReach >= nums.length - 1)
                return true;
        }
        
        return false;
    }
}