Flipping Coins
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

Question

Flipping Coins

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.

Accepted Answer

Brute force

The idea is to check every subarray.
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.
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.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, only a constant extra space is required.

Time Complexity: O(1)Explanation:

O(N^2) per test case, where N is the number of coins.

In the worst case, we will be traversing all the possible subarrays. Thus, we will need 2 nested loops for start and end. Hence, O(N^2).

Accepted Answer

Subarray sum

The idea is to use the Kadane algorithm to find out the subarray with the maximum number of tails and a minimum number of heads. For example: Let's take the input array as { 1, 0, 1, 0, 0, 0, 1, 0}.
The maximum sum can be found by taking coins with the original tail side up as +1 and coins with the original head side up as -1. Thus, We will see this as an array of 1 and -1 where 0 means tail side up and is considered as ‘+1’ and 1 means head side up will be considered as ‘-1’. Hence, the array given in the above example becomes { -1, 1, -1, 1, 1, 1, -1, 1}.
Now, all we need to do is apply Kadane and find the maximum subarray sum. By applying Kadane's algorithm in the above example, we get Max sum = 3, for these subarrays, arr[1...5], arr[3...5], arr[1...7], and arr[3...7] (0 based-indexing).
We return the sum of the initial number of heads and the maximum subarray sum obtained.
The initial number of heads = 3, Maximum subarray sum = 3. Answer = 3+3 = 6. As let us choose arr[3...5](can choose any of the above subarrays) to do one flip, after flipping coins from index 3 to index 5, we get {1, 0, 1, 1, 1, 1, 1, 0} which gives us the maximum number of head side up coins, i.e., 6.