Largest subarray sum of all connected components in undirected graph

0 0 11 minutes read

Given an undirected graph with V vertices and E edges, the task is to find the maximum contiguous subarray sum among all the connected components of the graph.

Examples:

Input: E = 4, V = 7

Output:
Maximum subarray sum among all connected components = 5
Explanation:
Connected Components and maximum subarray sums are as follows:
[3, 2]: Maximum subarray sum = 3 + 2 = 5
[4, -2, 0]: Maximum subarray sum = 4
[-1, -5]: Maximum subarray sum = -1
So, Maximum contiguous subarray sum = 5

Input: E = 6, V = 10

Output:
Maximum subarray sum among all connected components = 9
Explanation:
Connected Components and maximum subarray sums are as follows:
[-3]: Maximum subarray sum = -3
[-2, 7, 1, -1]: Maximum subarray sum = 7 + 1 = 8
[4, 0, 5]: Maximum subarray sum = 4 + 0 + 5 = 9
[-4, 6]: Maximum subarray sum = 6
So, Maximum contiguous subarray sum = 9

Approach: The idea is to use Depth First Search Traversal to keep track of the connected components in the undirected graph as explained in this article. For each connected component, the array is analyzed and the maximum contiguous subarray sum is computed based on Kadane’s Algorithm as explained in this article. A global variable is set that is compared at each iteration with the local sum values to obtain the final result.

Below is the implementation of the above approach:

C++

// C++ implementation to find
// largest subarray sum among
// all connected components
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to traverse the undirected
// graph using the Depth first traversal
void depthFirst(int v, vector<int> graph[],
                vector<bool>& visited,
                vector<int>& storeChain)
{
    // Marking the visited
    // vertex as true
    visited[v] = true;
 
    // Store the connected chain
    storeChain.push_back(v);
 
    for (auto i : graph[v]) {
        if (visited[i] == false) {
 
            // Recursive call to
            // the DFS algorithm
            depthFirst(i, graph,
                       visited, storeChain);
        }
    }
}
 
// Function to return maximum
// subarray sum of each connected
// component using Kadane's Algorithm
int subarraySum(int arr[], int n)
{
    int maxSubarraySum = arr[0];
    int currentMax = arr[0];
 
    // Following loop finds maximum
    // subarray sum based on Kadane's
    // algorithm
    for (int i = 1; i < n; i++) {
        currentMax = max(arr[i],
                         arr[i] + currentMax);
 
        // Global maximum subarray sum
        maxSubarraySum = max(maxSubarraySum,
                             currentMax);
    }
 
    // Returning the sum
    return maxSubarraySum;
}
 
// Function to find the maximum subarray
// sum among all connected components
void maxSubarraySum(
    vector<int> graph[], int vertices,
    vector<int> values)
{
    // Initializing boolean array
    // to mark visited vertices
    vector<bool> visited(1001, false);
 
    // maxSum stores the
    // maximum subarray sum
    int maxSum = INT_MIN;
 
    // Following loop invokes DFS algorithm
    for (int i = 1; i <= vertices; i++) {
        if (visited[i] == false) {
 
            // Variable to hold
            // temporary length
            int sizeChain;
 
            // Variable to hold temporary
            // maximum subarray sum values
            int tempSum;
 
            // Container to store each chain
            vector<int> storeChain;
 
            // DFS algorithm
            depthFirst(i, graph, visited, storeChain);
 
            // Variable to hold each chain size
            sizeChain = storeChain.size();
 
            // Container to store values
            // of vertices of individual chains
            int chainValues[sizeChain + 1];
 
            // Storing the values of each chain
            for (int i = 0; i < sizeChain; i++) {
                int temp = values[storeChain[i] - 1];
                chainValues[i] = temp;
            }
 
            // Function call to find maximum
            // subarray sum of current connection
            tempSum = subarraySum(chainValues,
                                  sizeChain);
 
            // Conditional to store current
            // maximum subarray sum
            if (tempSum > maxSum) {
                maxSum = tempSum;
            }
        }
    }
 
    // Printing global maximum subarray sum
    cout << "Maximum subarray sum among all ";
    cout << "connected components = ";
    cout << maxSum;
}
 
// Driver code
int main()
{
    // Initializing graph in the
    // form of adjacency list
    vector<int> graph[1001];
 
    // Defining the number
    // of edges and vertices
    int E, V;
    E = 4;
    V = 7;
 
    // Assigning the values for each
    // vertex of the undirected graph
    vector<int> values;
    values.push_back(3);
    values.push_back(2);
    values.push_back(4);
    values.push_back(-2);
    values.push_back(0);
    values.push_back(-1);
    values.push_back(-5);
 
    // Constructing the undirected graph
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[3].push_back(4);
    graph[4].push_back(3);
    graph[4].push_back(5);
    graph[5].push_back(4);
    graph[6].push_back(7);
    graph[7].push_back(6);
 
    maxSubarraySum(graph, V, values);
    return 0;
}

Java

// Java implementation to find
// largest subarray sum among
// all connected components
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to traverse the undirected
// graph using the Depth first traversal
static void depthFirst(int v, List<List<Integer>> graph,
                       boolean[] visited, 
                       List<Integer> storeChain)
{
  // Marking the visited
  // vertex as true
  visited[v] = true;
 
  // Store the connected chain
  storeChain.add(v);
 
  for (int i : graph.get(v)) 
  {
    if (visited[i] == false) 
    {
      // Recursive call to
      // the DFS algorithm
      depthFirst(i, graph, 
                 visited, 
                 storeChain);
    }
  }
}
 
// Function to return maximum
// subarray sum of each connected
// component using Kadane's Algorithm
static int subarraySum(int arr[], 
                       int n)
{
  int maxSubarraySum = arr[0];
  int currentMax = arr[0];
 
  // Following loop finds maximum
  // subarray sum based on Kadane's
  // algorithm
  for (int i = 1; i < n; i++) 
  {
    currentMax = Math.max(arr[i], arr[i] + 
                          currentMax);
 
    // Global maximum subarray sum
    maxSubarraySum = Math.max(maxSubarraySum, 
                              currentMax);
  }
 
  // Returning the sum
  return maxSubarraySum;
}
 
// Function to find the maximum subarray
// sum among all connected components
static void maxSubarraySum(List<List<Integer>> graph,
                           int vertices,
                           List<Integer> values)
{
  // Initializing boolean array
  // to mark visited vertices
  boolean[] visited = new boolean[1001];
 
  // maxSum stores the
  // maximum subarray sum
  int maxSum = Integer.MIN_VALUE;
 
  // Following loop invokes DFS 
  // algorithm
  for (int i = 1; i <= vertices; i++) 
  {
    if (visited[i] == false) 
    {
      // Variable to hold
      // temporary length
      int sizeChain;
 
      // Variable to hold temporary
      // maximum subarray sum values
      int tempSum;
 
      // Container to store each chain
      List<Integer> storeChain = 
           new ArrayList<Integer>();
 
      // DFS algorithm
      depthFirst(i, graph, 
                 visited, storeChain);
 
      // Variable to hold each 
      // chain size
      sizeChain = storeChain.size();
 
      // Container to store values
      // of vertices of individual chains
      int[] chainValues = 
            new int[sizeChain + 1];
 
      // Storing the values of each chain
      for (int j = 0; j < sizeChain; j++) 
      {
        int temp = values.get(storeChain.get(j) - 1);
        chainValues[j] = temp;
      }
 
      // Function call to find maximum
      // subarray sum of current connection
      tempSum = subarraySum(chainValues, 
                            sizeChain);
 
      // Conditional to store current
      // maximum subarray sum
      if (tempSum > maxSum) 
      {
        maxSum = tempSum;
      }
    }
  }
 
  // Printing global maximum subarray sum
  System.out.print("Maximum subarray sum among all ");
  System.out.print("connected components = ");
  System.out.print(maxSum);
}
 
// Driver code
public static void main(String[] args)
{
  // Initializing graph in the
  // form of adjacency list
  List<List<Integer>> graph = 
       new ArrayList();
 
  for (int i = 0; i < 1001; i++)
    graph.add(new ArrayList<Integer>());
 
  // Defining the number
  // of edges and vertices
  int E = 4, V = 7;
 
  // Assigning the values for each
  // vertex of the undirected graph
  List<Integer> values = 
       new ArrayList<Integer>();
   
  values.add(3);
  values.add(2);
  values.add(4);
  values.add(-2);
  values.add(0);
  values.add(-1);
  values.add(-5);
 
  // Constructing the undirected
  // graph
  graph.get(1).add(2);
  graph.get(2).add(1);
  graph.get(3).add(4);
  graph.get(4).add(3);
  graph.get(4).add(5);
  graph.get(5).add(4);
  graph.get(6).add(7);
  graph.get(7).add(6);
 
  maxSubarraySum(graph, V, values);
}
}
 
// This code is contributed by jithin

Python3

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

C#

// C# implementation to find
// largest subarray sum among
// all connected components
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
  
// Function to traverse the undirected
// graph using the Depth first traversal
static void depthFirst(int v, List<List<int>> graph,
                       bool[] visited, 
                       List<int> storeChain)
{
   
  // Marking the visited
  // vertex as true
  visited[v] = true;
   
  // Store the connected chain
  storeChain.Add(v);
  
  foreach (int i in graph[v]) 
  {
    if (visited[i] == false) 
    {
       
      // Recursive call to
      // the DFS algorithm
      depthFirst(i, graph, 
                 visited, 
                 storeChain);
    }
  }
}
  
// Function to return maximum
// subarray sum of each connected
// component using Kadane's Algorithm
static int subarraySum(int []arr, 
                       int n)
{
  int maxSubarraySum = arr[0];
  int currentMax = arr[0];
   
  // Following loop finds maximum
  // subarray sum based on Kadane's
  // algorithm
  for(int i = 1; i < n; i++) 
  {
    currentMax = Math.Max(arr[i], arr[i] + 
                          currentMax);
     
    // Global maximum subarray sum
    maxSubarraySum = Math.Max(maxSubarraySum, 
                              currentMax);
  }
   
  // Returning the sum
  return maxSubarraySum;
}
  
// Function to find the maximum subarray
// sum among all connected components
static void maxSubarraySum(List<List<int>> graph,
                           int vertices,
                           List<int> values)
{
   
  // Initializing boolean array
  // to mark visited vertices
  bool[] visited = new bool[1001];
  
  // maxSum stores the
  // maximum subarray sum
  int maxSum = -1000000;
  
  // Following loop invokes DFS 
  // algorithm
  for(int i = 1; i <= vertices; i++) 
  {
    if (visited[i] == false) 
    {
       
      // Variable to hold
      // temporary length
      int sizeChain;
       
      // Variable to hold temporary
      // maximum subarray sum values
      int tempSum;
  
      // Container to store each chain
      List<int> storeChain = new List<int>();
       
      // DFS algorithm
      depthFirst(i, graph, 
                 visited, storeChain);
  
      // Variable to hold each 
      // chain size
      sizeChain = storeChain.Count;
  
      // Container to store values
      // of vertices of individual chains
      int[] chainValues = new int[sizeChain + 1];
  
      // Storing the values of each chain
      for(int j = 0; j < sizeChain; j++) 
      {
        int temp = values[storeChain[j] - 1];
        chainValues[j] = temp;
      }
  
      // Function call to find maximum
      // subarray sum of current connection
      tempSum = subarraySum(chainValues, 
                            sizeChain);
  
      // Conditional to store current
      // maximum subarray sum
      if (tempSum > maxSum) 
      {
        maxSum = tempSum;
      }
    }
  }
   
  // Printing global maximum subarray sum
  Console.Write("Maximum subarray sum among all ");
  Console.Write("connected components = ");
  Console.Write(maxSum);
}
  
// Driver code
public static void Main(string[] args)
{
   
  // Initializing graph in the
  // form of adjacency list
  List<List<int>> graph = new List<List<int>>();
   
  for(int i = 0; i < 1001; i++)
    graph.Add(new List<int>());
  
  // Defining the number
  // of edges and vertices
  int V = 7;
  
  // Assigning the values for each
  // vertex of the undirected graph
  List<int> values = new List<int>();
   
  values.Add(3);
  values.Add(2);
  values.Add(4);
  values.Add(-2);
  values.Add(0);
  values.Add(-1);
  values.Add(-5);
  
  // Constructing the undirected
  // graph
  graph[1].Add(2);
  graph[2].Add(1);
  graph[3].Add(4);
  graph[4].Add(3);
  graph[4].Add(5);
  graph[5].Add(4);
  graph[6].Add(7);
  graph[7].Add(6);
  
  maxSubarraySum(graph, V, values);
}
}
 
// This code is contributed by pratham76

Javascript

<script>
    // Javascript implementation to find
    // largest subarray sum among
    // all connected components
     
    // Function to traverse the undirected
    // graph using the Depth first traversal
    function depthFirst(v, graph, visited, storeChain)
    {
 
      // Marking the visited
      // vertex as true
      visited[v] = true;
 
      // Store the connected chain
      storeChain.push(v);
 
      for(let i = 0; i < graph[v].length; i++)
      {
        if (visited[graph[v][i]] == false)
        {
 
          // Recursive call to
          // the DFS algorithm
          depthFirst(graph[v][i], graph,
                     visited,
                     storeChain);
        }
      }
    }
 
    // Function to return maximum
    // subarray sum of each connected
    // component using Kadane's Algorithm
    function subarraySum(arr, n)
    {
      let maxSubarraySum = arr[0];
      let currentMax = arr[0];
 
      // Following loop finds maximum
      // subarray sum based on Kadane's
      // algorithm
      for(let i = 1; i < n; i++)
      {
        currentMax = Math.max(arr[i], arr[i] +
                              currentMax);
 
        // Global maximum subarray sum
        maxSubarraySum = Math.max(maxSubarraySum,
                                  currentMax);
      }
 
      // Returning the sum
      return maxSubarraySum;
    }
 
    // Function to find the maximum subarray
    // sum among all connected components
    function maxSubarraySum(graph, vertices, values)
    {
 
      // Initializing boolean array
      // to mark visited vertices
      let visited = new Array(1001);
      visited.fill(false);
 
      // maxSum stores the
      // maximum subarray sum
      let maxSum = -1000000;
 
      // Following loop invokes DFS
      // algorithm
      for(let i = 1; i <= vertices; i++)
      {
        if (visited[i] == false)
        {
 
          // Variable to hold
          // temporary length
          let sizeChain;
 
          // Variable to hold temporary
          // maximum subarray sum values
          let tempSum;
 
          // Container to store each chain
          let storeChain = [];
 
          // DFS algorithm
          depthFirst(i, graph,
                     visited, storeChain);
 
          // Variable to hold each
          // chain size
          sizeChain = storeChain.length;
 
          // Container to store values
          // of vertices of individual chains
          let chainValues = new Array(sizeChain + 1);
 
          // Storing the values of each chain
          for(let j = 0; j < sizeChain; j++)
          {
            let temp = values[storeChain[j] - 1];
            chainValues[j] = temp;
          }
 
          // Function call to find maximum
          // subarray sum of current connection
          tempSum = subarraySum(chainValues,
                                sizeChain);
 
          // Conditional to store current
          // maximum subarray sum
          if (tempSum > maxSum)
          {
            maxSum = tempSum;
          }
        }
      }
 
      // Printing global maximum subarray sum
      document.write("Maximum subarray sum among all ");
      document.write("connected components = ");
      document.write(maxSum);
    }
     
    // Initializing graph in the
    // form of adjacency list
    let graph = [];
 
    for(let i = 0; i < 1001; i++)
      graph.push([]);
 
    // Defining the number
    // of edges and vertices
    let V = 7;
 
    // Assigning the values for each
    // vertex of the undirected graph
    let values = [];
 
    values.push(3);
    values.push(2);
    values.push(4);
    values.push(-2);
    values.push(0);
    values.push(-1);
    values.push(-5);
 
    // Constructing the undirected
    // graph
    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);
 
// This code is contributed by suresh07.
</script>

Output

Maximum subarray sum among all connected components = 5

Time Complexity: O(V²)
The DFS algorithm takes O(V + E) time to run, where V, E are the vertices and edges of the undirected graph. Further, the maximum contiguous subarray sum is found at each iteration that takes an additional O(V) to compute and return the result based on Kadane’s Algorithm. Hence, the overall complexity is O(V²)
Auxiliary Space: O(V)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!