algorithm - LinkedIn Coding Round

Question

An array containing only 0s and 1s is given as input. You can pick any two indices of the array i and j and flip all the elements between them ( i.e 0->1 and 1->0). Find maximum sum of the array which can be obtained after the flip. Ex: For [0,1,0,0,1,0], The answer is 4.(Flip from index 2 to 3).

Here is my approach:
1)Find the prefix sum ( keep in sum[i]) for all indices in the array.
2)Flip all the bits in the original array.
3)Use Kadane's algo to find the max subarray sum MAXSUM.Let the start and end indices of the max subarray be i and j.
4)The answer is sum(i-1)+MAXSUM+sum(n-1)-sum(j).

Please tell me if my approach is right.

Answer 1

Actually, you can do this really easily in one pass over the array. You keep track of how good your current range of flipped bits is doing. As long as you are in the positive, the current range is good to prepend to any subsequent range. But once you get to zero or negative, you should discard your range and start a new range.

For example, if you find that flipping indices 0..5 results in +4, then this is good and you would want to keep 0..5 as part of your range because it will only benefit you if you are also going to flip indices 6..X. But if 0..5 results in -1, you want to not use 0..5 because that will just lower your score. So at that point you would start over at 6..6. Maybe it's easier to see in the code. Here is a C version that solves the problem in one pass:

// Returns best range (start..end) to flip, and best score achieved.
static void findRange(const int *array, int *pStart, int *pEnd, int *pScore)
{
    int start     = 0;
    int best      = 0;
    int i         = 0;
    int diff      = 0;
    int base      = 0;
    int bestStart = -1;
    int bestEnd   = -1;

    // Count the number of 1s in the array already.
    for (i=0;i<N;i++)
        base += array[i];

    // Run through the array, keeping track of "diff", which is how much
    // we have gained by flipping the bits from "start" to "i".
    for (i=start=0;i<N;i++) {
        // Flip the number at i.
        if (array[i] == 0)
            diff++;
        else
            diff--;
        // If this range (from start to i) is the best so far, remember it.
        if (diff > best) {
            bestStart = start;
            bestEnd   = i;
            best      = diff;
        }
        // If we get to a zero or negative difference, start over with a
        // new range starting from i+1.
        if (diff <= 0) {
            start = i+1;
            diff  = 0;
        }
    }
    *pStart = bestStart;
    *pEnd   = bestEnd;
    *pScore = base + best;
}

Edit: After reading about Kadane's algorithm, it turns out that what I wrote is equivalent using Kadane's to find the maximum subarray on a modified array where you switch each 0 to 1 and each 1 to -1.