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

• 아무 수를 최대 K개 삭제할 수 있다고 하지만, 짝수 부분수열의 길이를 길게 하기 위해서는 당연하게도 홀수만 K번 삭제해야 한다.
• 그렇다면 문제는, 홀수를 K개 포함하는 부분수열중에서 가장 긴 것을 찾는 문제가 되고, 이것은 투 포인터를 사용하면 O(n)에 푸는 것이 가능하다
• 하지만 좀더 간단하게 푸는 방법도 가능한데, 주어진 배열에서 각각의 인접한 홀수와 홀수 사이에 짝수가 몇개씩 들어있는지를 세어서 그것으로 배열을 만드는 것이다. 이렇게 만든 배열에서 길이가 K+1인 부분배열의 합은, 원래 배열에서 홀수 K개를 포함한 부분수열의 길이와 같다. 길이가 K+1인 부분배열들에 대해서만 합을 구해보면 되는데, 이렇게 길이가 고정이 되어있는 경우는 슬라이딩 윈도우 방식으로 구현하면 되기 때문에 코드가 간단해진다. 또한 누적합 배열로 바꿔서 처리하면 부분배열의 합을 구하는 것도 더욱 간단해진다. 시간복잡도는 O(n)으로 동일하지만 좀더 빠르다.

"""Solution code for "BOJ 22857. 가장 긴 짝수 연속한 부분 수열 (small)".

- Problem link: https://www.acmicpc.net/problem/22857
- Solution link: http://www.teferi.net/ps/problems/boj/22857
"""


def main():
    N, K = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    S = [int(x) for x in input().split()]

    even_counts = [0]
    count = 0
    for num in S:
        if num % 2:
            even_counts.append(count)
        else:
            count += 1
    even_counts.append(count)

    answer = max((r - l for l, r in zip(even_counts, even_counts[K + 1:])),
                 default=even_counts[-1])
    print(answer)


if __name__ == '__main__':
    main()