Longest Alternating Sequence with One Flip#9556
Murad has a collection of coins arranged in a row on a table. Each coin shows either heads () or tails (). Murad wants to create the longest possible contiguous alternating sequence of coins (for example, or ), where adjacent coins differ.
To do this, he may choose at most one contiguous subarray of coins and flip all of them (changing heads to tails and tails to heads). Help Murad determine the maximum length of a contiguous alternating subarray he can get after performing at most one such flip.
The first line contains an integer (1 \leq N \leq 10^5), the number of coins.
The next line contains numbers, each being or .
Output the maximum length of the alternating contiguous subarray that can be obtained after flipping at most one subarray.
Example 1
Example 2
First Test Case:
If you flip the coins from indices to , the array becomes: 1\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 1\ 0. The highlighted part is alternating and has length .
Second Test Case:
Only change the -th index: 1\ 0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1.