<섹션3-Two pointers, Sliding window> 6. 최대 길이 연속부분수열

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

<설명>

0과 1로 구성된 길이가 N인 수열이 주어집니다. 여러분은 이 수열에서 최대 k번을 0을 1로 변
경할 수 있습니다. 여러분이 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의
연속부분수열을 찾는 프로그램을 작성하세요.
만약 길이가 길이가 14인 다음과 같은 수열이 주어지고 k=2라면
1 1 0 0 1 1 0 1 1 0 1 1 0 1
여러분이 만들 수 있는 1이 연속된 연속부분수열은 1 1 0 0 1 1 1 1 1 1 1 1 0 1 이며 그
길이는 8입니다.

<입력>

첫 번째 줄에 수열의 길이인 자연수 N(5<=N<100,000)이 주어집니다.
두 번째 줄에 N길이의 0과 1로 구성된 수열이 주어집니다.

<출력>

첫 줄에 최대 길이를 출력하세요.

===================================================

<코드>

for문을 활용하여 0을 만나면 cnt를 증가시킨다. cnt의 값이 특정 값보다 커지면 시작부분부터 while문을 활용하여 0을 다시 만나면 cnt를 감소시킨다. 최대길이는 rt-lt+1로 구하는 것이 효율적이다.

import java.util.*;

class Main {	
	public int solution(int n,int k,int[] array){
		int answer=0,lt=0,cnt=0;
		for(int rt=0;rt<n;rt++) {
			if(array[rt]==0) cnt++;
			while(cnt>k) {
				if(array[lt]==0) cnt--;
				lt++;
				
			}
			answer=Math.max(answer, rt-lt+1);
		}
	
	
		return answer;
	}
		
		
	public static void main(String[] args) {
		Main main = new Main();
		Scanner scan = new Scanner(System.in);
		
		int n=scan.nextInt();
		int k=scan.nextInt();
		int[] array=new int[n];
		for(int i=0;i<n;i++) {
			array[i]=scan.nextInt();
		}
		
		System.out.print(main.solution(n,k,array));
		}
}

<중요>

1) rt-lt+1로 최대길이를 구할 수 있다.