Why is this failing?


#1

Your submission failed for the following input:

A : "010"

Your function returned the following :

1 3

The expected returned value :

1 1


#2

“010” can be flipped the following two ways to give maximal sum (number of ones):
(1,1) flip -> “110”
(1,3) flip -> “101”
However (1,1) is lexicographically smaller than (1,3) [ Which is required by the problem ] and therefore is the output.

The following code is a modified version of Kadane’s Algorithm for finding maximal subarray implemented in C++ and runs in O(n) time complexity

vector Solution::flip(string A) {

int max_so_far = 0;
int mx1 = -1, mx2 = -1;
int max_end_here = 0;
int x1 = 0, x2 = -1;
for(int i=0;i<A.length();i++)
{
	x2++;
	if(A.at(i)=='1')
		max_end_here -= 1;
	else
		max_end_here += 1;
	if(max_end_here<0)
	{
		max_end_here = 0;
		x1 = i+1;
		x2 = i;
	}
	if(max_end_here>max_so_far)
	{
		max_so_far = max_end_here;
		mx1 = x1+1;
		mx2 = x2+1;
	}
}
vector<int> v;
if(mx1<0 || mx2<0) return v;
v.push_back(mx1);
v.push_back(mx2);
return v;

}

PS : Apologies for the messy variable names!