Maximize number of 0s by flipping a subarray in java

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