CareerCup

This is a special case of the maximum subarray problem. It can be solved in O(n) with a modified version of Kadane's algorithm where 0's are treated as 1 and 1's as -1.

public int maximumOnes(int a[]) {
		int onesCount = 0;
		int maxEndingHere = 0;
		int maxSoFar = 0;
		for (int i = 0; i < a.length; ++i) {
			if (a[i] == 1) {
				onesCount++;
			}
			maxEndingHere += a[i] == 1 ? -1 : 1;
			if (maxEndingHere <= 0) {
				maxEndingHere = 0;
			}
			else if (maxEndingHere > maxSoFar) {
				maxSoFar = maxEndingHere;
			}
		}
		return onesCount + maxSoFar;
	}

Seems to look like:
1) Find the most-left 0. sum = 1, left = i, max = 1, ansleft = i, ansright = i
2) Go right bit by bit while sum > 0:
a[i] == 0 -> sum++
renew max, ansleft and ansright if needed
a[i] == 1 -> sum--
if sum == 0
find next 0 and start from it.

final answer = number of 1 outside the [ansleft, ansright] + max.

Simple O(N) algo.

Python code: Runs in O(N)
Assumes the input is stored in an array named "arr".
I have kept the code simple for ease of understanding.

prevptr = 0
ptr     = 0		# counter variable for parsing the array
newval  = 0	# keeps track of num_zeros - num_ones
optL    = 0 	# keeps track of left side of opt
optR    = 0 	# keeps track of right side of opt
opt     = 0		# optimum
countone= 0	# How many one's we find in array

while ptr < len(arr):

    # change newval depending on the new element
    if arr[ptr]:
        newval   -= 1
        countone += 1
    else:
        newval += 1

    if newval <= 0:	# Ah! We found useless interval
        prevptr = ptr+1     # useless interval, move prevptr ahead
        newval  = 0
        
    if newval > opt:    # if newval is more than opt, change opt
        opt  = newval
        optL = prevptr
        optR = ptr

    ptr += 1

outside_ones = countone - ((optR - optL + 1) - opt)/2
print "Ones after change= ", opt+outside_ones, " optL = ",optL, " optR = ",optR

make each as -1 and each 0 as +1 now the question becomes find maximum sum in subarray, Let me know if it doesn't work.

Thank you for the replies. I haven't gone through 3rd and 4th solutions. For 1st and 2nd, it looks good. Both approaches look similar with different ways of coding. I just had one small doubt here,

With your approach, consider following example,
1 0 0 1 1 0

We start with index 1 (as first 0). We pass 4th index and say the sum is 0, and hence cancel the window and start with another 0, which is index 5. So, now our window becomes [5,5], which will make the array as 1 0 0 1 1 1
Output: max 1's = 4.

But our window should have been [1,2], which will make the array as 1 1 1 1 1 0
Output: max 1's = 5.

python:

import random
arr = [random.randint(0,1) for x in range(10)]
 
end = 0
cur_total = 0
best_max = 0
for idx, val in enumerate(arr):
    cur_total = max(0, cur_total + (1 if val == 0 else -1))
    if cur_total > best_max:
        best_max = cur_total
        end = idx
 
start = 0
cur_total = 0
best_max = 0
for idx, val in enumerate(reversed(arr)):
    cur_total = max(0, cur_total + (1 if val == 0 else -1))
    if cur_total > best_max:
        best_max = cur_total
        tmp = (len(arr) - 1) - idx
        if tmp <= end:
            start = tmp
 
num_ones = best_max + sum([x for x in arr[0:start] if x == 1]) + sum([x for x in arr[end-1:-1] if x == 1])
print arr
print num_ones
print (start, end)