Algorithm - LinkedIn Coding Cycle

Question

An input containing only 0 and 1 is indicated as input. You can select any two indexes of the array i and j and flip all the elements between them (for example, 0-> 1 and 1-> 0). Find the maximum amount of the array that can be obtained after the flip. Example: for [0,1,0,0,1,0] the answer is 4. (Flip from index 2 to 3).

Here is my approach:
 1) Find the sum of the prefix (keep in the sum of [i]) for all indices in the array.
                   2) Flip all the bits in the source array.
                   3) Use Kadane algo to find the maximum amount of Subarray MAXSUM. Let the initial and final indices of the maximum subarray be equal to i and j.
                   4) The answer is the sum (i-1) + MAXSUM + sum (n-1) -sum (j).

Please tell me if my approach is correct.

Answer 1

, . , . , . , .

, , 0..5 +4, , 0..5 , , 6..X. 0..5 -1, 0..5, . 6..6. , . C, :

// 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: , , , Kadane , 0 1 1 -1.