Query to find length of the longest subarray consisting only of 1 s | Java Program for the above approach ; Arrays to store prefix sums , suffix and MAX 's node respectively ; Function to conSegment Tree ; MAX array for node MAX ; Array for prefix sum node ; Array for suffix sum node ; Calculate MAX node ; Function to update Segment Tree ; Update at position ; Update sums from bottom to the top of Segment Tree ; Update MAX tree ; Update pref tree ; Update suf tree ; Function to perform given queries ; Stores count of queries ; Traverse each query ; Print longest length of subarray in [ 1 , N ] ; Flip the character ; Driver Code ; Size of array ; Given array ; Given queries ; Number of queries
import java . util . * ; class GFG { static final int INF = 1000000 ; static int [ ] pref = new int [ 500005 ] ; static int [ ] suf = new int [ 500005 ] ; static int [ ] MAX = new int [ 500005 ] ; static void build ( int a [ ] , int tl , int tr , int v ) { if ( tl == tr ) { MAX [ v ] = a [ tl ] ; pref [ v ] = a [ tl ] ; suf [ v ] = a [ tl ] ; } else { int tm = ( tl + tr ) / 2 ; build ( a , tl , tm , v * 2 ) ; build ( a , tm + 1 , tr , v * 2 + 1 ) ; MAX [ v ] = Math . max ( MAX [ v * 2 ] , Math . max ( MAX [ v * 2 + 1 ] , suf [ v * 2 ] + pref [ v * 2 + 1 ] ) ) ; pref [ v ] = Math . max ( pref [ v * 2 ] , pref [ 2 * v ] + ( pref [ 2 * v ] == ( tm - tl + 1 ) ? 1 : 0 ) * pref [ v * 2 + 1 ] ) ; suf [ v ] = Math . max ( suf [ v * 2 + 1 ] , suf [ 2 * v + 1 ] + suf [ v * 2 ] * ( suf [ 2 * v + 1 ] == ( tr - tm ) ? 1 : 0 ) ) ; } } static void update ( int a [ ] , int pos , int tl , int tr , int v ) { if ( tl > pos tr < pos ) { return ; } if ( tl == tr && tl == pos ) { MAX [ v ] = a [ pos ] ; pref [ v ] = a [ pos ] ; suf [ v ] = a [ pos ] ; } else { int tm = ( tl + tr ) / 2 ; update ( a , pos , tl , tm , v * 2 ) ; update ( a , pos , tm + 1 , tr , v * 2 + 1 ) ; MAX [ v ] = Math . max ( MAX [ v * 2 ] , Math . max ( MAX [ v * 2 + 1 ] , suf [ v * 2 ] + pref [ v * 2 + 1 ] ) ) ; pref [ v ] = Math . max ( pref [ v * 2 ] , pref [ 2 * v ] + ( pref [ 2 * v ] == ( tm - tl + 1 ) ? 1 : 0 ) * pref [ v * 2 + 1 ] ) ; suf [ v ] = Math . max ( suf [ v * 2 + 1 ] , suf [ 2 * v + 1 ] + ( suf [ 2 * v + 1 ] == ( tr - tm ) ? 1 : 0 ) * suf [ v * 2 ] ) ; } } static void solveQueries ( int arr [ ] , int n , int [ ] [ ] Q , int k ) { int cntQuery = Q . length ; build ( arr , 0 , n - 1 , 1 ) ; for ( int i = 0 ; i < cntQuery ; i ++ ) { if ( Q [ i ] [ 0 ] == 1 ) { System . out . print ( MAX [ 1 ] + " ▁ " ) ; } else { arr [ Q [ i ] [ 1 ] - 1 ] ^= 1 ; update ( arr , Q [ i ] [ 1 ] - 1 , 0 , n - 1 , 1 ) ; } } } public static void main ( String [ ] args ) { int N = 10 ; int arr [ ] = { 1 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 } ; int [ ] [ ] Q = { { 1 } , { 2 , 3 } , { 1 } } ; int K = 3 ; solveQueries ( arr , N , Q , K ) ; } }