arrays - algorithm - LinkedIn Coding Round -

an array containing 0s , 1s given input. can pick 2 indices of array , j , flip elements between them ( i.e 0->1 , 1->0). find maximum sum of array can obtained after flip. ex: [0,1,0,0,1,0], answer 4.(flip index 2 3).

here approach:
1)find prefix sum ( keep in sum[i]) indices in array.
2)flip bits in original array.
3)use kadane's algo find max subarray sum maxsum.let start , end indices of max subarray , j.
4)the answer sum(i-1)+maxsum+sum(n-1)-sum(j).

please tell me if approach right.

actually, can in 1 pass on array. keep track of how current range of flipped bits doing. long in positive, current range prepend subsequent range. once 0 or negative, should discard range , start new range.

for example, if find flipping indices 0..5 results in +4, , want keep 0..5 part of range because benefit if going flip indices 6..x. if 0..5 results in -1, want not use 0..5 because lower score. @ point start on @ 6..6. maybe it's easier see in code. here c version solves problem in 1 pass:

// returns best range (start..end) flip, , best score achieved. static void findrange(const int *array, int *pstart, int *pend, int *pscore) {     int start     = 0;     int best      = 0;     int         = 0;     int diff      = 0;     int base      = 0;     int beststart = -1;     int bestend   = -1;      // count number of 1s in array already.     (i=0;i<n;i++)         base += array[i];      // run through array, keeping track of "diff", how     // have gained flipping bits "start" "i".     (i=start=0;i<n;i++) {         // flip number @ i.         if (array[i] == 0)             diff++;         else             diff--;         // if range (from start i) best far, remember it.         if (diff > best) {             beststart = start;             bestend   = i;             best      = diff;         }         // if 0 or negative difference, start on         // new range starting i+1.         if (diff <= 0) {             start = i+1;             diff  = 0;         }     }     *pstart = beststart;     *pend   = bestend;     *pscore = base + best; } 

edit: after reading kadane's algorithm, turns out wrote equivalent using kadane's find maximum subarray on modified array switch each 0 1 , each 1 -1.