# Flipping Coins

Moderate
0/80
Average time to solve is 32m
Contributed by

## Problem statement

Gary has N coins placed in a straight line. Some coins have head side up, and others have the tail side up.

Convention:
``````1 denotes the HEAD side is up.
0 denotes the TAIL side is up.
``````

Now, Gary wants to obtain a maximum number of head-side up coins. He can perform at most one(possibly 0) flip in which he can flip the coins of a continuous interval (continuous subarray).

For example: In the given array (0 based indexing), { 1, 0, 0, 1, 0, 0, 1 }, we can obtain maximum head side up coins by flipping the coins in range 1 to 5. The array will thus become {1, 1, 1, 0, 1, 1, 1 }.

Return the maximum number of heads side up Gary can obtain.

Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <=10
1 <= N <= 10^5
0 <= arr[i] <= 1

where 'T' is the number of test cases, 'N' is the total number of coins, and 'arr[i]' denotes whether the coin is head side up or tail side up.
Time limit: 1 sec.
``````
##### Sample input 1:
``````1
4
1 0 1 0
``````
##### Sample output 1:
``````3
``````
##### Explanation
``````{ 1, 1, 1, 0} is one possible answer if we flip range 1-1.
``````
##### Sample input 2:
``````2
5
0 0 1 0 1
3
1 1 1
``````
##### Sample output 2:
``````4
3
``````
Console