Maximum Number of 1s Geeks Solution

Maximum Number of 1s Geeks Solution

  December 28, 2017    

---

Idea is to find maximum zero - 1 count for every position from i to j
At last add this to max number of 1

O(n) Approach

Code:
import java.util.*;
import java.lang.*;
import java.io.*;
class max1inOneMove
 {
public static int max1inOneMove(String str)
{
int max=0;
int len=str.length();
int zero=0,one=0;
int zcount[]=new int[len+1];
int ocount[]=new int[len+1];
for(int i=0;i<len;++i)
{
if(str.charAt(i)=='1')
{
++one;
ocount[i+1]=one;
zcount[i+1]=zero;
}
if(str.charAt(i)=='0')
{
++zero;
ocount[i+1]=one;
zcount[i+1]=zero;
}
}
if(one==len)
return len-1;
if(zero==len)
return len;
for(int i=1;i<=len;++i)
for(int j=i;j<=len;++j)
{
max=Math.max(max,(zcount[j]-zcount[i-1])-(ocount[j]-ocount[i-1]));
}
return max+ocount[len];
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    System.out.println(max1inOneMove(ab.next()));
}
}
}