Find number of bits to be flipped to get maximum 1's in array

Question

We have a bit array like below

{1 0 1 0 0 1 0 1}

Number of bits in above array is 8

If we take range from [1,5] then number of bits in [1,5] range is [0 1 0 0 1].
If we flip this range then after flipping it will be [ 1 0 1 1 0]
So total number of 1's after flipping [1,5] range is [1 1 0 1 1 0 0 1] = 5

If we take range from [1,6] then number of bits in [1,6] range is [0 1 0 0 1 0].
If we flip this range then after flipping it will be [ 1 0 1 1 0 1]
So total number of 1's after flipping [1,5] range is [1 1 0 1 1 0 1 1] = 6

So the answer is range [1,6] and after flipping we can get 6 1's in array

Is there a good algorithm that can solve this problem. I an only think of dynamic programming because this problem can be broken down into sub problems which can be combined.

Answer 1

Inspired by @Nabbs comment, there is an easy way to solve this in linear time: by reducing the problem to maximal segment sum.

Transform all 0s to 1s and all 1s to -1s. The problem is then the same as minimizing the sum of the array after transforming. (the minimal sum contains most -1s in the transformed array, which corresponds to most 1s in the original problem).

We can calculate the sum as

sum(after flipping) = sum(non-flipped) - sum(flipped part before flipping)

because the sum of the flipped part is inverted. If we now express the non-flipped part as follows:

sum(non-flipped) = sum(original array) - sum(flipped part before flipping)

we find that we need to minimize

sum(after flipping) = sum(original array) - 2 sum(flipped part before flipping)

The first part is a constant, so we really need to maximize the sum of the flipped part. This is exactly what the maximum segment sum problem does.

---

I wrote a lengthy derivation on how to solve that problem in linear time a while ago, so now I'll only share the code. Below I updated the code to also store the boundaries. I chose javascript as the language, because it is so easy to test in the browser and because I don't have to make the types of variables x and y explicit.

var A = Array(1, 0, 1, 0, 0, 1, 0, 1);
var sum = 0;

// count the 1s in the original array and
// do the 0 -> 1 and 1 -> -1 conversion
for(var i = 0; i < A.length; i++) {
    sum += A[i];
    A[i] = A[i] == 0 ? 1 : -1;        
}

// find the maximum subarray
var x = { value: 0, left: 0, right: 0 };
var y = { value: 0, left: 0 };
for (var n = 0; n < A.length; n++) {
    // update y
    if (y.value + A[n] >= 0) {
        y.value += A[n];
    } else {
        y.left = n+1;
        y.value = 0;
    }
    // update x
    if (x.value < y.value) {
        x.left = y.left;
        x.right = n;
        x.value = y.value;
    }
}

// convert the result back
alert("result = " + (sum + x.value) 
    + " in range [" + x.left + ", " + x.right + "]");

You can easily verify this in your browser. For instance in Chrome, press F12, click Console and paste this code. It should output

result = 6 in range [1, 4]