[22857] 가장 긴 짝수 연속한 부분 수열 (small)

https://www.acmicpc.net/problem/22857

22857번: 가장 긴 짝수 연속한 부분 수열 (small)

<문제>

투포인터로 해결할 수 있다.

구간 [i, j]에 cnt개의 홀수가 존재한다면, score는 (j - i + 1) - cnt이고, 이것이 구간 [i, j]에서의 최적해이다.

이를 바탕으로 score의 최대값을 투포인터의 탐색과정동안 업데이트해주었다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, k, a[50001];
bool flag;
int main(void) {
    cin >> n >> k;
    int i, j;
    for (i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] % 2 == 0) flag = true;
    }
    i = j = 0;
    int cnt = a[0] % 2;
    int ans = 0;
    while (i <= j && j < n) {
        if (cnt <= k && j + 1 < n) {
            j++;
            if (a[j] % 2 == 1) {
                cnt++;
            }
        } else {
            if (a[i] % 2 == 1) {
                cnt--;
            }
            i++;
        }
        if (cnt <= k) {
            int score = (j - i + 1) - cnt;
            ans = max(score, ans);
        }
    }
    if (flag) ans = max(1, ans);
    cout << ans;
    return 0;
}