Jump Game

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.

For example:

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

The idea is use greed algorithm to jump to the next farthest element in the array with max(A[i]+i). Why do we need to also include the index? because if index is large means you are more close to the end. Some edge cases:

1. Do not jump to an element with array[i]==0
2. If you can jump to the end of the array, return true
3. After checking, if no available jump found (all 0s), return false.

public boolean canJump(int[] A) {
        if (A==null||A.length==0) {
            return false;
        }

        int index = 0;
        while(index<A.length-1) {
            int canJump = A[index]+index;
            int nextJumpIndex = 0;
            int maxJump = 0;

            for (int i=index+1; i<=Math.min(canJump, A.length-1); i++) {
                if (i==A.length-1) {
                    return true;
                }

                if (A[i]!=0&&maxJump<A[i]+i) {
                    maxJump = A[i]+i;
                    nextJumpIndex = i;
                }
            }

            if (index<nextJumpIndex) {
                index = nextJumpIndex;
            } else {
                return false;
            }
        }

        return true;
    }