New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Flipping Coins

Contributed by

Ashwani

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 32 mins

Success Rate 68 %

8 upvotes

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 )

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.

Sample input 1:

1
4
1 0 1 0

Sample output 1:

Explanation

{ 1, 1, 1, 0} is one possible answer if we flip range 1-1.

Sample input 2:

Sample output 2:

4
3

Autocomplete

Console