MaximizeZeros.js

// Maximize number of 0s by flipping a subarray

// 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.

// 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



////Analysis
/// basically the question is to find maximum number of subsequent 1s in an array
/// if we find the longest subarray of 1 , we know that flipping it would result in maximum zeros
/// in this case the maximum zeros will be the current number of zeros + longest subarray of 1

/// function below is O(N) way of finding longest subarray of 1
function maxNumberOfOnesSubArray(inputArray) {
	var startIndex=-1;
	var endIndex=-1;
	var curIdxSize=0;
	var maxIdxSize=0;
	for(i=0;i<inputArray.length;i++) {
		if (inputArray[i] == 1) {
			if(startIndex==-1 || (i-endIndex) > 1) {
				startIndex=i;
				endIndex=i;
			}
			else if(startIndex > -1) {
				endIndex=i;
			}
			continue;
		}
		else {
			curIdxSize = endIndex - startIndex;
			if (curIdxSize >maxIdxSize) 
				maxIdxSize = curIdxSize;
		}
	}
	if (endIndex == i-1) {
		curIdxSize = endIndex - startIndex;
		if (curIdxSize >maxIdxSize) 
			maxIdxSize = curIdxSize;
	}
	return maxIdxSize+1;
}


/// function below counts the number of zeros in input array
function countZeros(inputArray) {
	var c=0;
	for(i=0;i<inputArray.length;i++) {
		if(inputArray[i] == 0) {
			c++;
		}
	}
	return c;
} 

//the solution is maxNumberOfOnesSubArray()+countZeros()

////////////////////////////
/////verfication
////////////////////////////
//example input arrays
console.log(countZeros([0, 1, 0, 0, 1, 1, 0])+maxNumberOfOnesSubArray([0, 1, 0, 0, 1, 1, 0]));
console.log(countZeros([0, 0, 0, 1, 0, 1])+maxNumberOfOnesSubArray([0, 0, 0, 1, 0, 1]));

//my own array
var x=[0,0,0,1,0,1,1,1,1,0,1,1,1,0,0,1,1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,0,0];
console.log(countZeros(x)+maxNumberOfOnesSubArray(x));