package leetcode;

/**
 * https://leetcode.com/problems/jump-game-ii/
 */
public class Problem45 {
    public int jump(int[] nums) {
        int result = 0;
        int i = 0;
        while (i < nums.length - 1) {
            int max = 0;
            int maxIdx = 0;
            for (int j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
                if (nums[j] >= max) {
                    max = nums[j];
                    maxIdx = j;
                }
            }
            result++;
            if (i + nums[i] >= nums.length - 1) {
                break;
            }
            i = maxIdx;
        }
        return result;
    }

    public static void main(String[] args) {
        Problem45 prob = new Problem45();
//        System.out.println(prob.jump(new int[]{2, 3, 1, 1, 4})); // 2
//        System.out.println(prob.jump(new int[]{2, 6, 1, 1, 4})); // 2
//        System.out.println(prob.jump(new int[]{2, 6, 1, 1, 4})); // 2
//        System.out.println(prob.jump(new int[]{2, 2, 3, 1, 2, 4, 1})); // 3
//        System.out.println(prob.jump(new int[]{100, 5, 1, 1, 4})); // 1
//        System.out.println(prob.jump(new int[]{5})); // 0
//        System.out.println(prob.jump(new int[]{2, 3, 1})); // 1
//        System.out.println(prob.jump(new int[]{1, 2, 1, 1, 1})); // 3
        System.out.println(prob.jump(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 0})); // 2
    }
}

@@ -223,18 +223,18 @@
     int 
-ma
+id
 x = 0;%0A 
@@ -248,19 +248,20 @@
     int 
-max
+next
 Idx = 0;
@@ -291,12 +291,8 @@
  = i
- + 1
 ; j 
@@ -353,16 +353,20 @@
     if (
+j + 
 nums%5Bj%5D 
@@ -366,20 +366,23 @@
 ums%5Bj%5D %3E
-= ma
+ nextId
 x) %7B%0A   
@@ -402,21 +402,15 @@
     
-ma
+id
 x = 
-nums%5Bj%5D
+j
 ;%0A  
@@ -431,18 +431,29 @@
     
-max
+next
 Idx = j
+ + nums%5Bj%5D
 ;%0A  
@@ -525,62 +525,50 @@
 f (i
- + nums%5Bi%5D %3E= nums.length - 1) %7B%0A                break
+dx == i) %7B%0A                i = i + nums%5Bi%5D
 ;%0A  
@@ -570,33 +570,44 @@
 %5D;%0A            %7D
-%0A
+ else %7B%0A    
             i = 
@@ -610,15 +610,26 @@
 i = 
-maxIdx;
+idx;%0A            %7D
 %0A   
@@ -900,80 +900,8 @@
 / 2%0A
-//        System.out.println(prob.jump(new int%5B%5D%7B2, 6, 1, 1, 4%7D)); // 2%0A
 //  
@@ -1108,18 +1108,16 @@
 ); // 0%0A
-//
         
@@ -1244,16 +1244,18 @@
 ); // 3%0A
+//
         
@@ -1338,16 +1338,110 @@
 ); // 2%0A
+//        System.out.println(prob.jump(new int%5B%5D%7B10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0%7D)); // 2%0A
     %7D%0A%7D%0A

Update problem 45