Largest subarray sum of all connected components in undirected graph | Python3 implementation to find largest subarray sum among all connected components ; Function to traverse the undirected graph using the Depth first traversal ; Marking the visited vertex as true ; Store the connected chain ; Recursive call to the DFS algorithm ; Function to return maximum subarray sum of each connected component using Kadane 's Algorithm ; Following loop finds maximum subarray sum based on Kadane 's  algorithm ; Global maximum subarray sum ; Returning the sum ; Function to find the maximum subarray sum among all connected components ; Initializing boolean array to mark visited vertices ; maxSum stores the maximum subarray sum ; Following loop invokes DFS algorithm ; Variable to hold temporary length ; Variable to hold temporary maximum subarray sum values ; Container to store each chain ; DFS algorithm ; Variable to hold each chain size ; Container to store values of vertices of individual chains ; Storing the values of each chain ; Function call to find maximum subarray sum of current connection ; Conditional to store current maximum subarray sum ; Printing global maximum subarray sum ; Initializing graph in the form of adjacency list ; Defining the number of edges and vertices ; Assigning the values for each vertex of the undirected graph ; Constructing the undirected graph
import sys NEW_LINE def depthFirst ( v , graph , visited , storeChain ) : NEW_LINE INDENT visited [ v ] = True ; NEW_LINE storeChain . append ( v ) ; NEW_LINE for i in graph [ v ] : NEW_LINE INDENT if ( visited [ i ] == False ) : NEW_LINE INDENT depthFirst ( i , graph , visited , storeChain ) ; NEW_LINE DEDENT DEDENT DEDENT def subarraySum ( arr , n ) : NEW_LINE INDENT maxSubarraySum = arr [ 0 ] ; NEW_LINE currentMax = arr [ 0 ] ; NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT currentMax = max ( arr [ i ] , arr [ i ] + currentMax ) NEW_LINE maxSubarraySum = max ( maxSubarraySum , currentMax ) ; NEW_LINE DEDENT return maxSubarraySum ; NEW_LINE DEDENT def maxSubarraySum ( graph , vertices , values ) : NEW_LINE INDENT visited = [ False for i in range ( 1001 ) ] NEW_LINE maxSum = - sys . maxsize ; NEW_LINE for i in range ( 1 , vertices + 1 ) : NEW_LINE INDENT if ( visited [ i ] == False ) : NEW_LINE INDENT sizeChain = 0 NEW_LINE tempSum = 0 ; NEW_LINE storeChain = [ ] ; NEW_LINE depthFirst ( i , graph , visited , storeChain ) ; NEW_LINE sizeChain = len ( storeChain ) NEW_LINE chainValues = [ 0 for i in range ( sizeChain + 1 ) ] ; NEW_LINE for i in range ( sizeChain ) : NEW_LINE INDENT temp = values [ storeChain [ i ] - 1 ] ; NEW_LINE chainValues [ i ] = temp ; NEW_LINE DEDENT tempSum = subarraySum ( chainValues , sizeChain ) ; NEW_LINE if ( tempSum > maxSum ) : NEW_LINE INDENT maxSum = tempSum ; NEW_LINE DEDENT DEDENT DEDENT print ( " Maximum ▁ subarray ▁ sum ▁ among ▁ all ▁ " , end = ' ' ) ; NEW_LINE print ( " connected ▁ components ▁ = ▁ " , end = ' ' ) NEW_LINE print ( maxSum ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT graph = [ [ ] for i in range ( 1001 ) ] NEW_LINE E = 4 ; NEW_LINE V = 7 ; NEW_LINE values = [ ] ; NEW_LINE values . append ( 3 ) ; NEW_LINE values . append ( 2 ) ; NEW_LINE values . append ( 4 ) ; NEW_LINE values . append ( - 2 ) ; NEW_LINE values . append ( 0 ) ; NEW_LINE values . append ( - 1 ) ; NEW_LINE values . append ( - 5 ) ; NEW_LINE graph [ 1 ] . append ( 2 ) ; NEW_LINE graph [ 2 ] . append ( 1 ) ; NEW_LINE graph [ 3 ] . append ( 4 ) ; NEW_LINE graph [ 4 ] . append ( 3 ) ; NEW_LINE graph [ 4 ] . append ( 5 ) ; NEW_LINE graph [ 5 ] . append ( 4 ) ; NEW_LINE graph [ 6 ] . append ( 7 ) ; NEW_LINE graph [ 7 ] . append ( 6 ) ; NEW_LINE maxSubarraySum ( graph , V , values ) ; NEW_LINE DEDENT