package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/max-consecutive-ones-iii/
 */
public class Problem1004 {
    public int longestOnes(int[] A, int K) {
        List<NumberCount> list = new ArrayList<>();
        for (int i = 0; i < A.length; i++) {
            if (A[i] == 0) {
                if (list.isEmpty()) {
                    list.add(new NumberCount(0, 1));
                    continue;
                }
                NumberCount nc = list.get(list.size() - 1);
                if (nc.number == A[i]) {
                    nc.count++;
                } else {
                    list.add(new NumberCount(0, 1));
                }
            } else {
                if (list.isEmpty()) {
                    list.add(new NumberCount(1, 1));
                    continue;
                }
                NumberCount nc = list.get(list.size() - 1);
                if (nc.number == A[i]) {
                    nc.count++;
                } else {
                    list.add(new NumberCount(1, 1));
                }
            }
        }
        int answer = 0;
        for (int i = 0; i < list.size(); i++) {
            NumberCount n = list.get(i);
            int max = 0;
            int count = K;
            if (n.number == 1) {
                max = n.count;
            } else {
                if (n.count - count >= 0) {
                    max = count;
                    count = 0;
                } else {
                    count -= n.count;
                    max = n.count;
                }
            }
            int j = i + 1;
            while (j < list.size()) {
                NumberCount nc = list.get(j);
                if (nc.number == 0) {
                    if (count - nc.count >= 0) {
                        count -= nc.count;
                        max += nc.count;
                    } else {
                        max += count;
                        break;
                    }
                } else {
                    max += nc.count;
                }
                j++;
            }
            answer = Math.max(answer, max);
        }
        return answer;
    }

    private static class NumberCount {
        private final int number;
        private int count;

        public NumberCount(int number, int count) {
            this.number = number;
            this.count = count;
        }

        @Override
        public String toString() {
            return number + ": " + count;
        }
    }

    public static void main(String[] args) {
        Problem1004 prob = new Problem1004();
//        System.out.println(prob.longestOnes(new int[]{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}, 2)); // 6
//        System.out.println(prob.longestOnes(new int[]{1, 1, 1}, 2)); // 3
//        System.out.println(prob.longestOnes(new int[]{0, 0, 0}, 3)); // 3
//        System.out.println(prob.longestOnes(new int[]{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}, 3)); // 10
//        System.out.println(prob.longestOnes(new int[]{0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, 3)); // 10
        System.out.println(prob.longestOnes(new int[]{1,0,0,0,1,1,0,0,1,1,0,0,0,0,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,1,0,0,1,1,0,1,1}, 8)); // 25
    }
}

@@ -1186,49 +1186,8 @@
 ) %7B%0A
-            NumberCount n = list.get(i);%0A
     
@@ -1251,57 +1251,100 @@
    i
-f (n.number == 1) %7B%0A                max = n.count
+nt j = i;%0A            while (j %3C list.size()) %7B%0A                NumberCount nc = list.get(j)
 ;%0A  
@@ -1349,33 +1349,54 @@
             
-%7D else %7B%0A
+    if (nc.number == 0) %7B%0A    
             
@@ -1407,18 +1407,16 @@
 if (
-n.
 count - 
 coun
@@ -1411,16 +1411,19 @@
 count - 
+nc.
 count %3E=
@@ -1448,22 +1448,32 @@
         
-max = 
+    count -= nc.
 count;%0A 
@@ -1495,19 +1495,33 @@
     
-count = 0;%0A
+    max += nc.count;%0A    
     
@@ -1565,26 +1565,104 @@
     
-count -= n.
+    max += 
 count;%0A
+                        break;%0A                    %7D%0A                %7D else %7B%0A
     
@@ -1681,19 +1681,21 @@
     max 
++
 = n
+c
 .count;%0A
@@ -1704,32 +1704,53 @@
               %7D%0A
+                j++;%0A
             %7D%0A  
@@ -1763,21 +1763,176 @@
     
+answer = Math.max(answer, max);%0A        %7D%0A        for (
 int 
-j = i + 1
+i = list.size() - 1; i %3E= 0; i--) %7B%0A            int max = 0;%0A            int count = K;%0A            int j = i
 ;%0A  
@@ -1946,37 +1946,28 @@
    while (j 
-%3C list.size()
+%3E= 0
 ) %7B%0A        
@@ -2384,34 +2384,34 @@
                j
-++
+--
 ;%0A            %7D%0A
@@ -2726,837 +2726,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return number + %22: %22 + count;%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1004 prob = new Problem1004();%0A//        System.out.println(prob.longestOnes(new int%5B%5D%7B1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0%7D, 2)); // 6%0A//        System.out.println(prob.longestOnes(new int%5B%5D%7B1, 1, 1%7D, 2)); // 3%0A//        System.out.println(prob.longestOnes(new int%5B%5D%7B0, 0, 0%7D, 3)); // 3%0A//        System.out.println(prob.longestOnes(new int%5B%5D%7B1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0%7D, 3)); // 10%0A//        System.out.println(prob.longestOnes(new int%5B%5D%7B0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1%7D, 3)); // 10%0A        System.out.println(prob.longestOnes(new int%5B%5D%7B1,0,0,0,1,1,0,0,1,1,0,0,0,0,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,1,0,0,1,1,0,1,1%7D, 8)); // 25
 %0A   

Solve problem 1004