Maximum sum of segments among all segments formed in array after Q queries | Python 3 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 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 sys NEW_LINE maxAns = - sys . maxsize - 1 NEW_LINE def Find ( parent , a ) : NEW_LINE INDENT if ( parent [ a ] == a ) : NEW_LINE INDENT return a NEW_LINE DEDENT return Find ( parent , parent [ a ] ) NEW_LINE DEDENT def Union ( parent , rank , setSum , a , b ) : NEW_LINE INDENT a = Find ( parent , a ) NEW_LINE b = Find ( parent , b ) NEW_LINE if ( a == b ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( rank [ a ] > rank [ b ] ) : NEW_LINE INDENT rank [ a ] += 1 NEW_LINE DEDENT if ( rank [ b ] > rank [ a ] ) : NEW_LINE INDENT swap ( a , b ) NEW_LINE DEDENT parent [ b ] = a NEW_LINE setSum [ a ] += setSum [ b ] NEW_LINE DEDENT def maxValues ( arr , queries , N ) : NEW_LINE INDENT global maxAns NEW_LINE rank = [ 0 ] * ( N + 1 ) NEW_LINE setSum = [ 0 ] * ( N + 1 ) NEW_LINE currMax = [ ] NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT parent [ i ] = - 1 NEW_LINE setSum [ i ] = arr [ i - 1 ] NEW_LINE DEDENT currMax . append ( 0 ) NEW_LINE for i in range ( N - 1 , 0 , - 1 ) : NEW_LINE INDENT if ( parent [ queries [ i ] ] == - 1 ) : NEW_LINE INDENT parent [ queries [ i ] ] = queries [ i ] NEW_LINE DEDENT if ( queries [ i ] - 1 >= 0 and parent [ queries [ i ] - 1 ] != - 1 ) : NEW_LINE INDENT Union ( parent , rank , setSum , queries [ i ] , queries [ i ] - 1 ) NEW_LINE DEDENT if ( queries [ i ] + 1 <= N and parent [ queries [ i ] + 1 ] != - 1 ) : NEW_LINE INDENT Union ( parent , rank , setSum , queries [ i ] , queries [ i ] + 1 ) NEW_LINE DEDENT maxAns = max ( setSum [ queries [ i ] ] , maxAns ) NEW_LINE currMax . append ( maxAns ) NEW_LINE DEDENT for i in range ( len ( currMax ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT print ( currMax [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 3 , 2 , 5 ] NEW_LINE queries = [ 3 , 4 , 1 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE maxValues ( arr , queries , N ) NEW_LINE DEDENT