Largest subarray sum of all connected components in undirected graph | 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
function depthFirst ( v , graph , visited , storeChain ) { visited [ v ] = true ; storeChain . push ( v ) ; for ( let i = 0 ; i < graph [ v ] . length ; i ++ ) { if ( visited [ graph [ v ] [ i ] ] == false ) { depthFirst ( graph [ v ] [ i ] , graph , visited , storeChain ) ; } } } function subarraySum ( arr , n ) { let maxSubarraySum = arr [ 0 ] ; let currentMax = arr [ 0 ] ; for ( let i = 1 ; i < n ; i ++ ) { currentMax = Math . max ( arr [ i ] , arr [ i ] + currentMax ) ; maxSubarraySum = Math . max ( maxSubarraySum , currentMax ) ; } return maxSubarraySum ; } function maxSubarraySum ( graph , vertices , values ) { let visited = new Array ( 1001 ) ; visited . fill ( false ) ; let maxSum = - 1000000 ; for ( let i = 1 ; i <= vertices ; i ++ ) { if ( visited [ i ] == false ) { let sizeChain ; let tempSum ; let storeChain = [ ] ; depthFirst ( i , graph , visited , storeChain ) ; sizeChain = storeChain . length ; let chainValues = new Array ( sizeChain + 1 ) ; for ( let j = 0 ; j < sizeChain ; j ++ ) { let temp = values [ storeChain [ j ] - 1 ] ; chainValues [ j ] = temp ; } tempSum = subarraySum ( chainValues , sizeChain ) ; if ( tempSum > maxSum ) { maxSum = tempSum ; } } } document . write ( " " ) ; document . write ( " " ) ; document . write ( maxSum ) ; } let graph = [ ] ; for ( let i = 0 ; i < 1001 ; i ++ ) graph . push ( [ ] ) ; let V = 7 ; let values = [ ] ; values . push ( 3 ) ; values . push ( 2 ) ; values . push ( 4 ) ; values . push ( - 2 ) ; values . push ( 0 ) ; values . push ( - 1 ) ; values . push ( - 5 ) ; graph [ 1 ] . push ( 2 ) ; graph [ 2 ] . push ( 1 ) ; graph [ 3 ] . push ( 4 ) ; graph [ 4 ] . push ( 3 ) ; graph [ 4 ] . push ( 5 ) ; graph [ 5 ] . push ( 4 ) ; graph [ 6 ] . push ( 7 ) ; graph [ 7 ] . push ( 6 ) ; maxSubarraySum ( graph , V , values ) ;