package leetcode;

/**
 * https://leetcode.com/problems/partition-array-into-disjoint-intervals/
 */
public class Problem915 {
    public int partitionDisjoint(int[] A) {
        int minIdx = 0;
        int maxIdx = 0;
        boolean smaller = true;
        int i = 1;
        int answer = 1;
        while (i < A.length) {
            if (smaller) {
                while (i < A.length && A[i] >= A[minIdx]) {
                    if (A[minIdx] > A[i]) {
                        minIdx = i;
                    }
                    if (A[maxIdx] < A[i]) {
                        maxIdx = i;
                    }
                    i++;
                }
            } else {
                while (i < A.length && A[i] < A[maxIdx]) {
                    if (A[minIdx] > A[i]) {
                        minIdx = i;
                    }
                    if (A[maxIdx] < A[i]) {
                        maxIdx = i;
                    }
                    i++;
                }
                answer = i;
            }
            smaller = !smaller;
            i++;
        }
        return answer;
    }

    public static void main(String[] args) {
        Problem915 prob = new Problem915();
//        System.out.println(prob.partitionDisjoint(new int[]{5, 0, 3, 8, 6})); // 3
//        System.out.println(prob.partitionDisjoint(new int[]{5, 0, 3, 6, 8})); // 3
//        System.out.println(prob.partitionDisjoint(new int[]{1, 1, 1, 0, 6, 12})); // 4
//        System.out.println(prob.partitionDisjoint(new int[]{1, 1, 1, 0, 6, 12, 3, 13})); // 4
//        System.out.println(prob.partitionDisjoint(new int[]{4, 10, 6, 2, 8, 12})); // 5
//        System.out.println(prob.partitionDisjoint(new int[]{5, 5, 3, 8, 2, 10, 9})); // 5
//        System.out.println(prob.partitionDisjoint(new int[]{1, 1})); // 1
//        System.out.println(prob.partitionDisjoint(new int[]{1, 1, 1, 2, 2, 2})); // 1
        System.out.println(prob.partitionDisjoint(new int[]{90, 47, 69, 10, 43, 92, 31, 73, 61, 97})); // 9
    }
}

@@ -176,19 +176,23 @@
     int 
-min
+prevMax
 Idx = 0;
@@ -204,17 +204,20 @@
     int 
-m
+curM
 axIdx = 
@@ -223,40 +223,8 @@
  0;%0A
-        boolean smaller = true;%0A
     
@@ -297,39 +297,8 @@
 ) %7B%0A
-            if (smaller) %7B%0A    
     
@@ -337,16 +337,18 @@
 %5Bi%5D 
-%3E= A%5Bmin
+%3C A%5BcurMax
 Idx%5D
@@ -371,35 +371,12 @@
     
-    if (A%5BminIdx%5D %3E A%5Bi%5D) %7B
+i++;
 %0A   
@@ -376,32 +376,34 @@
 ++;%0A            
+%7D%0A
             minI
@@ -390,38 +390,38 @@
   %7D%0A            
-minIdx
+answer
  = i;%0A          
@@ -426,188 +426,59 @@
     
-        %7D%0A                    if (A%5BmaxIdx%5D %3C A%5Bi%5D) %7B%0A                        maxIdx = i;%0A                    %7D%0A                    i++;%0A                %7D%0A            %7D else %7B%0A    
+prevMaxIdx = curMaxIdx;%0A            curMaxIdx = i;%0A
     
@@ -517,13 +517,18 @@
 %5Bi%5D 
-%3C A%5Bm
+%3E= A%5BprevM
 axId
@@ -553,133 +553,30 @@
     
-    
 if (A%5B
-minIdx%5D %3E A%5Bi%5D) %7B%0A                        minIdx = i;%0A                    %7D%0A                    if (A%5BmaxIdx%5D %3C A%5Bi
+i%5D %3E A%5BcurMaxIdx
 %5D) %7B
@@ -600,13 +600,12 @@
     
-    m
+curM
 axId
@@ -619,36 +619,32 @@
                 
-    
 %7D%0A              
@@ -637,36 +637,32 @@
                 
-    
 i++;%0A           
@@ -666,1042 +666,59 @@
     
-    %7D%0A                answer = i;%0A            %7D%0A            smaller = !smaller;%0A            i++;%0A        %7D%0A        return answer;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem915 prob = new Problem915();%0A//        System.out.println(prob.partitionDisjoint(new int%5B%5D%7B5, 0, 3, 8, 6%7D)); // 3%0A//        System.out.println(prob.partitionDisjoint(new int%5B%5D%7B5, 0, 3, 6, 8%7D)); // 3%0A//        System.out.println(prob.partitionDisjoint(new int%5B%5D%7B1, 1, 1, 0, 6, 12%7D)); // 4%0A//        System.out.println(prob.partitionDisjoint(new int%5B%5D%7B1, 1, 1, 0, 6, 12, 3, 13%7D)); // 4%0A//        System.out.println(prob.partitionDisjoint(new int%5B%5D%7B4, 10, 6, 2, 8, 12%7D)); // 5%0A//        System.out.println(prob.partitionDisjoint(new int%5B%5D%7B5, 5, 3, 8, 2, 10, 9%7D)); // 5%0A//        System.out.println(prob.partitionDisjoint(new int%5B%5D%7B1, 1%7D)); // 1%0A//        System.out.println(prob.partitionDisjoint(new int%5B%5D%7B1, 1, 1, 2, 2, 2%7D)); // 1%0A        System.out.println(prob.partitionDisjoint(new int%5B%5D%7B90, 47, 69, 10, 43, 92, 31, 73, 61, 97%7D)); // 9
+%7D%0A            i++;%0A        %7D%0A        return answer;
 %0A   

Solve problem 915