# Maximize number of 0s by flipping a subarray

Given a binary array, find the maximum/total number of zeros (not necessarily continuous) 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 subarray {1, 1} Input : arr[] = {0, 0, 0, 1, 0, 1} Output : 5

Approach: Count the continuous maximum no of 1's similar to Kadane's algorithm. The result will be then the total continuous 1's+total 0's in the array.

public static void main(String[] args) {

int a[] = { 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0 };

int min = a[0], max_1s_till_now = a[0];

int zeroes = 0;

for (int i : a) {

if (i == 0) {

min = 0;

zeroes++;

continue;

}

min = max(min, min + i);

max_1s_till_now = max(max_1s_till_now, min);

}

System.out.println(max_1s_till_now + zeroes);

}

private static int max(int i, int j) {

return i > j ? i : j;

}

}

## No comments:

## Post a Comment