카드 뒤집기 게임

면접 대비

시간 제한1초메모리 제한1024 MB

요약

이진 카드 배열에서 최대 한 번 앞에서부터 X번째까지 뒤집어 같은 값이 연속된 가장 긴 구간의 길이를 최대로 만든다.

문제

카드 뒤집기 게임은 $N$ 개의 카드를 이용해서 진행하는 게임이다. 각 카드에는 $1$ 부터 $N$ 까지의 번호가 순서대로 매겨져 있으며 앞면은 흰색, 뒷면은 검은색이다. 초기에, $N$ 개의 카드는 앞면 또는 뒷면으로 놓여있다.

이 게임의 목표는 가장 높은 점수를 얻는 것이다. 점수는 색깔이 같은 연속된 카드 구간 중 가장 긴 길이로 정의한다.

최대 한 번, $N$ 이하의 양의 정수 $X$ 를 골라서 $1$ 번부터 $X$ 번까지의 카드를 모두 뒤집을 수 있다.

이때, 카드 뒤집기 게임에서 얻을 수 있는 점수의 최댓값을 구하여라.

첫 번째 줄에는 카드의 개수를 나타내는 정수 $N(1 \le N \le 300,000)$ 이 주어진다.

두 번째 줄에는 $N$ 개의 카드의 초기 상태 $A\_1, A\_2, A\_3, ... , A\_{N}$ 이 공백으로 구분되어 주어진다.

$0$ 이면 카드의 초기 상태가 앞면임을, $1$ 이면 초기 상태가 뒷면임을 나타낸다.

카드 뒤집기 게임에서 얻을 수 있는 점수의 최댓값을 출력한다.