Question:

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.

Thinking:

It’s a problem can be solved in greedy algorithm. Because we should go as far as possible in current position until we can’t go father. And we should gurantee the value of current position + i (steps can be reached from current postion) + nums[cur + i] be as big as possible.

Solution:

public boolean canJump(int[] nums) {
    int l = nums.length;
    if (nums[0] == 0 && l > 1)
        return false;
    int cur = 0;
    int temp = nums[0];
    int step = nums[0];
    int max = nums[0];
    int tempcur = 0;

    while (cur + step < l-1){
        for (int i = 1; i <= step; i++){
            temp = cur + i + nums[cur + i];
            if (temp >= max){//current max greedy value
                max = temp;
                if (max >= l)
                    return true;
                tempcur = cur + i;
            }
        }
        if (cur == tempcur)
            return false;
        cur = tempcur;
        step = nums[cur];
    }

    if (max >= l-1)
        return true;
    else
        return false;
}

What’s more, we can make it easier by max the value of index.

public boolean canJump(int[] nums) {
    if(nums.length <= 1)
        return true;

    int max = nums[0]; //max stands for the largest index that can be reached.

    for(int i=0; i<nums.length; i++){
        //if not enough to go to next
        if(max <= i && nums[i] == 0) 
            return false;

        //update max    
        if(i + nums[i] > max){
            max = i + nums[i];
        }

        //max is enough to reach the end
        if(max >= nums.length-1) 
            return true;
    }

    return false;    
}