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] 

Answer 2

The solution uses Kadane's Algorithm.

We have to pick that substring where there are maximum number of 0s and minimum number of 1s, i.e., substring with max(count(0)-count(1)). So that after the flip, we can get maximum number of 1s in the final string.

Iterate over the string and keep a count. Increment this count whenever we encounter a 0 and decrement it when we encounter 1. The substring which will have the maximum value of this count will be our answer.

Here's a video by alGOds which explains the approach nicely. Do watch it if you have any doubts.

Link : https://youtu.be/cLVpE5q_-DE