[Greedy] Jump Game

1. Example
Basic Idea: do you still have moves >= 0
You are 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
s = [2,3,1,1,4] , return true
s= [3,2,1,0,4], return false

2. Implementation
Q1: jump? reach the last index?
A1: last Index =< current Index + s[current Index]. So s[i]+i is the maximum you can get
Q1:[2,A,B] ?
A1: you can go A and start from there or you can go B and start from there
Q1:[2,0,1,2]
A1: if you go to 0, unable to reach des. If you go to 1, you are able to do it.
total index 3
idx0 2 = 2 max
idx1 0 = 0 2 max-1 = 1 > 0
idx2 1 = 3 1max-1 = 0 < 3 max
idx3 2 = 5 3max-1= 2
out of loop true
 [3,2,1,0,4]
total index 4
idx0 3 =3 max
idx1 2 =3  3max- 1=2 ==2
idx2 1 =1   2max-1 =1 ==1
idx3 0        1mx-1 =0 == 0
idx4 4         0mx-1 < 0 false

// Time:O(n) ,Space:O(1)
public boolean canJump(int[] nums)
{
       // validate the input
       if ( nums == null || nums.length == 0)
            return false;
 


       int maxJump = nums[0];
       for (int i =1 ; i < nums.length; i++)
       {
            maxJump--;
            if (maxJump < 0)
                return false;
            if ( nums[i] > maxJump )
                maxJump = nums[i];

       }



       return true;



}

int reach = 0;// start from index 0
for (int i =0; i<= reach; && i < nums.length -1; i++)
{
      reach = Math.max(nums[i]+i, reach);
}



if ( reach < nums.length -1) // need to equal or larger than len-1 = last index
{
   return false;
}
else 
   return true; 

// Time:O(n^2)
nested loop 
for (i = 0; i< )
  for (j = 1; j< num[i])

3. Similar Ones

[Greedy] Best Time to Buy and Sell Stock II