Maximum number of 0s by flipping a subarray

http://www.geeksforgeeks.org/maximize-number-0s-flipping-subarray/

• The main idea here is looking at ever possible range within the array and seeing if the number of ones within that range is more than the number of zeros. If so, we want to flip that subarray then compare that difference with the original number of zeros. This will give us the maximum number of possible zeroes.
• This gives us an O(N^2) solution.

O(N^2) Solution

int maxZerosSubarray(vector<int> nums) {
    int origNumZeroes = 0;
    int maxDiff = 0;

    for(int i = 0; i < nums.size(); i++) {
        if(nums[i] == 0) {
            origNumZeroes++;
        }
        int numZeroes = 0;
        int numOnes = 0;
        for(int j = i; k < nums.size(); j++) {
            if(nums[j] == 0)
                numZeroes++;
            else
                numOnes++;

            maxDiff = max(maxDiff, numOnes - numZeroes);
        }
    }
    // This gives us all the zeroes within the array
    // with the zeroes within that subarray removed
    // by calculating the difference
    return origNumZeroes + maxDiff
}

O(N) Solution

• This method uses Kadane's algorithm by calulating the largest subarray sum. We then use this value combined with the number of zeroes to calculate the largest number of ones we can get within a range so we can flip those values. Because we want to see ones and subtract if we zero, we give one a value of one and zero a value of -1.

int maxZeroSubArray(vector<int> arr) {
    int origNumZeroes = 0;
    int maxDiff = 0;
    int currMax = 0;

    for(int i = 0; i < arr.size(); i++) {
        if(arr[i] == 0)
            origNumZeroes++;

        int val = 0;
        if(arr[i] == 1)
            val = 1;
        else
            val = -1;

        currMax = max(val, val + currMax);
        maxDiff = max(maxDiff, currMax);
    }
    // Is this value going to be greater than 0?
    maxDiff = max(0, maxDiff);
    return origNumZeroes + maxDiff;
}