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 = 5Input: 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 traversalvoid 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 Algorithmint 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 componentsvoid 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 codeint 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 componentsimport java.io.*;import java.util.*;class GFG{// Function to traverse the undirected// graph using the Depth first traversalstatic 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 Algorithmstatic 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 componentsstatic 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 codepublic 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 componentsimport sys # Function to traverse # the undirected graph # using the Depth first # traversaldef 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 Algorithmdef 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 componentsdef 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 componentsusing System;using System.Collections;using System.Collections.Generic;class GFG{ // Function to traverse the undirected// graph using the Depth first traversalstatic 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 Algorithmstatic 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 componentsstatic 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 codepublic 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(V2)
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(V2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
