Flipping Coins

Posted: 9 Oct, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.

Input format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the test cases follow.

The first line of each test case or query contains an integer 'N' representing the number of coins.

The second line contains 'N' single space-separated integers (0 or 1) representing the upside of the coins.
Output format:
For each test case, print the count of maximum head side up coins that can be obtained in a single line.

Output for each test case will be printed in a separate line.
Note
You are not required to print anything, and it has already been taken care of. Just implement the function.
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.
Approach 1
  1. The idea is to check every subarray.
  2. We can count the number of heads and number tails in every subarray and then calculate the maximum number of heads side up we can obtain if we flip that particular subarray.
  3. We also keep a count of the final start index and final end index that will give us the number of heads side up we can obtain later.
Try Problem