Maximum sum of segments among all segments formed in array after Q queries | Java program for the above approach ; Stores the maximum integer of the sets for each query ; Function to perform the find operation of disjoint set union ; Function to perform the Union operation of disjoint set union ; Find the parent of a and b ; Update the parent ; Update the sum of set a ; Function to find the maximum element from the sets after each operation ; Stores the parent elements of the sets ; Stores the rank of the sets ; Stores the sum of the sets ; Stores the maximum element for each query ; Initially set is empty ; Update the sum as the current element ; After the last query set will be empty and sum will be 0 ; Check if the current element is not in any set then make parent as current element of the queries ; Check left side of the queries [ i ] is not added in any set ; Add the queries [ i ] and the queries [ i ] - 1 in one set ; Check right side of the queries [ i ] is not added in any set ; Add queries [ i ] and the queries [ i ] + 1 in one set ; Update the maxAns ; Push maxAns to the currMax ; Print currMax values in the reverse order ; Driver Code
import java . util . * ; class GFG { static int maxAns = Integer . MIN_VALUE ; static int Find ( int [ ] parent , int a ) { return parent [ a ] = ( parent [ a ] == a ) ? a : ( Find ( parent , parent [ a ] ) ) ; } static void Union ( int [ ] parent , int [ ] rank , int [ ] setSum , int a , int b ) { a = Find ( parent , a ) ; b = Find ( parent , b ) ; if ( a == b ) return ; if ( rank [ a ] > rank [ b ] ) rank [ a ] ++ ; if ( rank [ b ] > rank [ a ] ) { int x = a ; a = b ; b = x ; } parent [ b ] = a ; setSum [ a ] += setSum [ b ] ; } static void maxValues ( int [ ] arr , int [ ] queries , int N ) { int [ ] parent = new int [ N + 1 ] ; int [ ] rank = new int [ N + 1 ] ; int [ ] setSum = new int [ N + 1 ] ; Vector < Integer > currMax = new Vector < Integer > ( ) ; for ( int i = 1 ; i < N + 1 ; i ++ ) { parent [ i ] = - 1 ; setSum [ i ] = arr [ i - 1 ] ; } currMax . add ( 0 ) ; for ( int i = N - 1 ; i > 0 ; i -- ) { if ( parent [ queries [ i ] ] == - 1 ) { parent [ queries [ i ] ] = queries [ i ] ; } if ( queries [ i ] - 1 >= 0 && parent [ queries [ i ] - 1 ] != - 1 ) { Union ( parent , rank , setSum , queries [ i ] , queries [ i ] - 1 ) ; } if ( queries [ i ] + 1 <= N && parent [ queries [ i ] + 1 ] != - 1 ) { Union ( parent , rank , setSum , queries [ i ] , queries [ i ] + 1 ) ; } maxAns = Math . max ( setSum [ queries [ i ] ] , maxAns ) ; currMax . add ( maxAns ) ; } for ( int i = currMax . size ( ) - 1 ; i >= 0 ; i -- ) { System . out . print ( currMax . get ( i ) + " ▁ " ) ; } } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 3 , 2 , 5 } ; int [ ] queries = { 3 , 4 , 1 , 2 } ; int N = arr . length ; maxValues ( arr , queries , N ) ; } }