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