3-6. 최대 길이 연속 부분수열

 

package 배열응용3장.최대길이연속부분수열3다시6.my;

import java.util.Scanner;

public class Main {

    /**
     * -내 풀이-
     * 0을 1로 바꾸는 작업을 하는 것에 초점이 맞아서 풀지 못했다.
     *
     * -피드백-
     * 0과 1로 바꾸는 작업 없이 start 와 end 와의 거리를 구하면 되는 것이다.
     * 또한 cnt 라는 개념을 추가하여 arr[end] == 0 이면 cnt++
     * 그리고 while (cnt > k) 로 cnt > k 인 상황에서 start 를 조정 (여기서 k 는 0을 1로 바꿀 수 있는 최대 횟수)
     * arr[start] == 1 이면 단순 start++ arr[start] == 0 이면 cnt-- 하면서 start++
     */

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        System.out.println(solution(n, k, arr));
    }

    private static int solution(int n, int k, int[] arr) {
        int answer = 0;
        int start = 0, end = 0, cnt = 0;

        while (start < n && end < n) {
            if (arr[end] == 0) {
                cnt++;
            }

            while (cnt > k) {
                if (arr[start] == 0) {
                    cnt--;
                }
                start++;
            }
            answer = Math.max(answer, end - start + 1);

            end++;
        }

        return answer;
    }
}