1004. Max Consecutive Ones III

처음 풀이 N^2

Runtime: 1000+ ms, faster than 100.00% of Java online submissions for Max Consecutive Ones III.

최적화 풀이 2N

Runtime: 7 ms, faster than 100.00% of Java online submissions for Max Consecutive Ones III.

풀이 방법

start 와 end 2개의 포지션을 가지고 구한다.

start 와 end 사이의 0 개수가 k 보다 적을때
-> end index를 늘림

회고

• 코드 if연산을 조금더 깔끔하게 할 수 있을것 같은데 쉽지가 않네

class Solution {
    public int longestOnes(int[] A, int K) {
       int zeroCount = 0;
        int max = 0;
        int startIndex = 0;

        for(int i=0; i<A.length; i++){
            if(A[i] == 1 ){
                max = Math.max(i+1 - startIndex, max) ;
                continue;
            }else {
                if(++zeroCount > K){                    
                
                    max = Math.max(i - startIndex, max) ;
                    sub:
                    for(; startIndex<=i; startIndex++){
                        if(A[startIndex] == 0){
                            zeroCount--;
                            startIndex++;
                            break sub;
                        }
                    }
                }
            }
        }
        max = Math.max(A.length - startIndex, max) ;
        return max;
    }
}