Maximize number of 0s by flipping a sub-array Given a binary array, find the maximum number zeros in an array with one flip of a sub-array allowed. A flip operation switches all 0s to 1s and 1s to 0s. Examples: Input : arr[] = {0, 1, 0, 0, 1, 1, 0} Output : 6 We can get 6 zeros by flipping the sub-array {1, 1} Input : arr[] = {0, 0, 0, 1, 0, 1} Output : 5 The idea is very simple just count the original zero and find the largest sum in the sub-array. i would provide a solution for it which will work in o(n) complexity. Solution: /** * @author Abhinaw.Tripathi * */ public class FlipZeroApp { public static void main(String[] args) { //int[] arr={0, 1, 0, 0, 1, 1, 0}; output should 6 int[] arr={0, 0, 0, 1, 0, 1}; // here output should be 5 int size=arr.length; int count=findMaxZeroCount(arr, size); System.out.println(count); } public static int findMaxZeroCount(int arr[], int n) { int orig_zero_count = 0; int max_diff = 0; int curr_max = 0; for (int i=0; i<n; i++) { 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 = Math.max(val, curr_max + val); max_diff = Math.max(max_diff, curr_max); } max_diff = Math.max(0, max_diff); return orig_zero_count + max_diff; } }
Complexity= o(n) , where as any other solution would work in o(n^2).
Output: 5