Longest subsequence possible that starts and ends with 1 and filled with 0 in the middle | Java program to find the longest subsequence possible that starts and ends with 1 and filled with 0 in the middle ; Prefix array to store the occurences of '1' and '0' ; Iterate over the length of the string ; If current character is '1' ; If current character is '0' ; Add '1' available for the first string ; Add '0' available for the second string ; Add '1' available for the third string ; Update answer ; Print the final result ; Driver code
import java . io . * ; class GFG { static void longestSubseq ( String s , int length ) { int [ ] ones = new int [ length + 1 ] ; int [ ] zeroes = new int [ length + 1 ] ; for ( int i = 0 ; i < length ; i ++ ) { if ( s . charAt ( i ) == '1' ) { ones [ i + 1 ] = ones [ i ] + 1 ; zeroes [ i + 1 ] = zeroes [ i ] ; } else { zeroes [ i + 1 ] = zeroes [ i ] + 1 ; ones [ i + 1 ] = ones [ i ] ; } } int answer = Integer . MIN_VALUE ; int x = 0 ; for ( int i = 0 ; i <= length ; i ++ ) { for ( int j = i ; j <= length ; j ++ ) { x += ones [ i ] ; x += ( zeroes [ j ] - zeroes [ i ] ) ; x += ( ones [ length ] - ones [ j ] ) ; answer = Math . max ( answer , x ) ; x = 0 ; } } System . out . println ( answer ) ; } public static void main ( String [ ] args ) { String s = "10010010111100101" ; int length = s . length ( ) ; longestSubseq ( s , length ) ; } }