Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Flipping Coins

Moderate
0/80
Average time to solve is 32m
profile
Contributed by
13 upvotes
Asked in companies
American ExpressWalmartFlipkart

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
Full screen
Console