# 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!