JAVA O(n) solution with explaination


#1
  1. If we are converting 0s to 1s then we need to consider the 1s that will be converted to 0s in our subarray. The idea is to select a subarray which has more 0s and less 1s so that after flipping, this subarray will increase the total number of 1s in our final array.

  2. By replacing all 1s with -1 and 0s with 1, the problem reduces down to finding the maximum sum subarray. Why because, we will be finding a subarray with maximum 0s and minimum 1s (which after flipping will yeild maximum 1s).

  3. For keeping track of start index and end index of our subarray, we take 2 variables and update them everytime we find a maximum subarray.

    public class Solution {
    public ArrayList flip(String A) {
    char[] a = A.toCharArray();
    int[] b = new int[a.length];
    for(int i=0;i<b.length;i++)
    {
    if(a[i] == ‘0’)
    {
    b[i] = 1;
    }
    else{
    b[i] = -1;
    }
    }
    int currsum = 0; int maxsum = Integer.MIN_VALUE;
    int start = 0; int end = 0; int s = 0;
    for(int i=0;i<b.length;i++)
    {
    currsum += b[i];
    if(currsum > maxsum)
    {
    maxsum = currsum;
    end = i;
    start = s;
    }
    if(currsum < 0)
    {
    currsum = 0;
    s = i+1;
    }
    }
    ArrayList output = new ArrayList<>();
    if(maxsum < 0)
    {
    return output;
    }
    output.add(start+1);
    output.add(end+1);
    return output;
    }
    }