## Friday, September 16, 2016

### Maximize number of 0s by flipping a subarray - GeeksforGeeks

Maximize number of 0s by flipping a subarray - GeeksforGeeks
Given a binary array, find the maximum number zeros in an array with one flip of a subarray allowed. A flip operation switches all 0s to 1s and 1s to 0s.

This problem can be reduced to largest subarray sum problem. The idea is to consider every 0 as -1 and every 1 as 1, find the sum of largest subarray sum in this modified array. This sum is our required max_diff ( count of 0s – count of 1s in any subarray). Finally we return the max_diff plus count of zeros in original array.
`// A Kadane's algorithm based solution to find maximum`
`// number of 0s by flipping a subarray.`
`int` `findMaxZeroCount(``bool` `arr[], ``int` `n)`
`{`
`    ``// Initialize count of zeros and maximum difference`
`    ``// between count of 1s and 0s in a subarray`
`    ``int` `orig_zero_count = 0;`
`    ``// Initiale overall max diff for any subarray`
`    ``int` `max_diff = 0;`
`    ``// Initialize current diff`
`    ``int` `curr_max = 0;`
`    ``for` `(``int` `i=0; i<n; i++)`
`    ``{`
`        ``// Count of zeros in original array (Not related`
`        ``// to Kadane's algorithm)`
`        ``if` `(arr[i] == 0)`
`           ``orig_zero_count++;`
`        ``// Value to be considered for finding maximum sum`
`        ``int` `val = (arr[i] == 1)? 1 : -1;`
`        ``// Update current max and max_diff`
`        ``curr_max = max(val, curr_max + val);`
`        ``max_diff = max(max_diff, curr_max);`
`    ``}`
`    ``max_diff = max(0, max_diff);`
`    ``return` `orig_zero_count + max_diff;`
`}`

http://buttercola.blogspot.com/2015/11/zenefits-flip-0-or-1.html
You are given an array a of sizeN. The elements of the array area[0], a[1], ... a[N - 1], where each a is either 0 or 1. You can perform one transformation on the array: choose any two integers L,and R, and flip all the elements between (and including) the Lth and Rth bits. In other words, Land R represent the left-most and the right-most index demarcating the boundaries of the segment whose bits you will decided to flip. ('Flipping' a bit means, that a 0 is transformed to a 1 and a 1 is transformed to a 0.)

What is the maximum number of '1'-bits (indicated by S) which you can obtain in the final bit-string?

` ``public` `static` `int` `countUneatenLeaves(``int``[] A) {`
`     ``if` `(A == ``null` `|| A.length == ``0``) {`
`         ``return` `0``;`
`     ``}`
`     `
`     ``int` `curSum = ``0``;`
`     ``int` `oneCount = ``0``;`
`     ``int` `minSum = Integer.MAX_VALUE;`
`     `
`     ``for` `(``int` `num : A) {`
`         ``if` `(num == ``0``) {`
`             ``curSum--;`
`         ``} ``else` `{`
`             ``curSum++;`
`             ``oneCount++;`
`         ``}`
`         `
`         ``if` `(curSum > ``0``) {`
`             ``curSum = ``0``;`
`         ``} ``else` `if` `(curSum < minSum) {`
`             ``minSum = curSum;`
`         ``}`
`     ``}`
`     `
`     ``return` `oneCount - curSum; // - minSum`

` ``}`

O(n^2)
A simple solution is to consider all subarrays and find a subarray with maximum value of (count of 1s) – (count of 0s). Let this value be max_diff. Finally return count of zeros in original array plus max_diff.

`// A Kadane's algorithm based solution to find maximum`
`// number of 0s by flipping a subarray.`
`int` `findMaxZeroCount(``bool` `arr[], ``int` `n)`
`{`
`    ``// Initialize max_diff = maximum of (Count of 0s -`
`    ``// count of 1s) for all subarrays.`
`    ``int` `max_diff = 0;`
`    ``// Initialize count of 0s in original array`
`    ``int` `orig_zero_count = 0;`
`    ``// Consider all Subarrays by using two nested two`
`    ``// loops`
`    ``for` `(``int` `i=0; i<n; i++)`
`    ``{`
`        ``// Increment count of zeros`
`        ``if` `(arr[i] == 0)`
`            ``orig_zero_count++;`
`        ``// Initialize counts of 0s and 1s`
`        ``int` `count1 = 0, count0 = 0;`
`        ``// Consider all subarrays starting from arr[i]`
`        ``// and find the difference between 1s and 0s.`
`        ``// Update max_diff if required`
`        ``for` `(``int` `j=i; j<n; j++)`
`        ``{`
`            ``(arr[j] == 1)? count1++ : count0++;`
`            ``max_diff = max(max_diff, count1 - count0);`
`        ``}`
`    ``}`
`    ``// Final result would be count of 0s in original`
`    ``// array plus max_diff.`
`    ``return` `orig_zero_count + max_diff;`
`}`

Related: Find zeroes to be flipped so that number of consecutive 1's is maximized
Maximize number of 0s by flipping a subarray