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

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]

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

The following code uses the trivial algorithm and runs in O(n²).

#include <iostream>
#include <bitset>
#include <utility>

typedef std::pair<unsigned, unsigned> range_t;

template <std::size_t N>
range_t max_flip(const std::bitset<N>& bs){
  int overall_score = 0;
  range_t result = range_t{0,0};

  for(std::size_t i = 0; i < N; ++i){
    int  score = bs[i] ? -1 : 1;
    auto max   = i;

    for(std::size_t j = i + 1; j < N; ++j){
      auto new_score = score + (bs[j] ? -1 : 1);

      if(new_score > score){
        score = new_score;
        max = j;
      }
    }
    if(score > overall_score){
      overall_score = score;
      result = {i,max};
    }
  }
  return result;
}

int main(){
  std::bitset<8> bitfield(std::string("10100101"));
  range_t range = max_flip(bitfield);
  std::cout << range.first << " .. " << range.second << std::endl;
}