Q52 Maximum difference of zeros and ones in binary string | Practice | GeeksforGeeks
Sat Apr 01 2023 05:46:20 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
//{ Driver Code Starts
//Initial Template for Java
import java.io.*;
import java.util.*;
class GFG {
public static void main(String args[]) throws IOException {
BufferedReader read =
new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(read.readLine());
while (t-- > 0) {
String s = read.readLine();
Solution ob = new Solution();
System.out.println(ob.maxSubstring(s));
}
}
}
// } Driver Code Ends
//User function Template for Java
class Solution {
int maxSubstring(String s) {
/* Q52 of dp playlist , making 0's to 1 and 1's to -1 and then applying
kadane's algo to find max sum sub array which will also give use the
max difference between 0's and 1's
*/
//applying kadanes
int csum = 0 , omax = Integer.MIN_VALUE;
for(int i =0 ; i < s.length() ; i++){
char ch = s.charAt(i);
int val = 0;
if(ch == '0')
val = 1;
else
val = -1;
if(csum > 0)
csum += val;
else
csum = val;
omax = Math.max(csum , omax);
}
return omax;
}
}
content_copyCOPY
https://practice.geeksforgeeks.org/problems/maximum-difference-of-zeros-and-ones-in-binary-string4111/1
Comments