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.
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?
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.
Related: Find zeroes to be flipped so that number of consecutive 1's is maximized
Maximize number of 0s by flipping a subarray
Read full article from 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
Read full article from Maximize number of 0s by flipping a subarray - GeeksforGeeks
