Thursday, June 15, 2017

Maximize number of 0s by flipping a subarray

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;
}
}

1 comment:

  1. Mysuru Casino - The HERZAMMAN
    Mysuru Casino herzamanindir - The Home kadangpintar of the Best of the Slots! Visit 토토사이트 us to Play the best slots 1등 사이트 and https://jancasino.com/review/merit-casino/ enjoy the best table games in our casino. Visit us

    ReplyDelete