Skip to main content

Flip Bits - Kadane's Algorithm

Problem Statement​

Given an array arr[] consisting of 0’s and 1’s. A flip operation is one in which you turn 1 into 0 and a 0 into 1. You have to do at most one “Flip” operation of any subarray. Formally, select a range (l, r) in the array arr[], such that 0 ≤ l ≤ r < n holds and flip the elements in this range to get the maximum ones in the final array. You can possibly make zero operations to get the answer.

Examples​

Example 1:

Input:
N = 5
A[] = {1, 0, 0, 1, 0} 
Output:
4
Explanation:
We can perform a flip operation in the range [1,2]
After flip operation array is : [ 1 1 1 1 0 ]
Count of one after fliping is : 4

Example 2:

Example 2:

Input:
N = 7
A[] = {1, 0, 0, 1, 0, 0, 1}
Output:
6
Explanation:
We can perform a flip operation in the range [1,5]
After flip operation array is : [ 1 1 1 0 1 1 1]
Count of one after fliping is : 6

Constraints​

  • 1 ≤ N ≤ 100
  • 0 ≤ arr[i] ≤ 1

Solution​

C++ Solution
#include <bits/stdc++.h>

int maxOnes(int arr[], int n)
{
    vector<int> A;
    int ones = accumulate(arr, arr+n, 0);

    int extra_ones = 0;
    int curr_extra_ones = 0;

    for(int i = 0; i < n; ++i) {
        int delta = arr[i] == 0 ? 1 : -1;

        if(curr_extra_ones + delta < delta) {
            curr_extra_ones = delta;
        }
        else {
            curr_extra_ones += delta;
        }
        extra_ones = max(extra_ones, curr_extra_ones);
    }

    return ones + extra_ones;
}