Dado un gráfico no dirigido con vértices V y aristas E , la tarea es encontrar la suma máxima de subarreglo contiguo entre todos los componentes conectados del gráfico.
Ejemplos:
Entrada: E = 4, V = 7
Salida:
suma máxima de subarreglo entre todos los componentes conectados = 5
Explicación:
los componentes conectados y las sumas máximas de subarreglo son las siguientes:
[3, 2]: suma máxima de subarreglo = 3 + 2 = 5
[4, -2, 0]: suma máxima de subarreglo = 4
[-1, -5]: suma máxima de subarreglo = -1
Entonces, suma máxima de subarreglo contiguo = 5Entrada: E = 6, V = 10
Salida:
suma máxima de subarreglo entre todos los componentes conectados = 9
Explicación:
los componentes conectados y las sumas máximas de subarreglo son las siguientes:
[-3]: suma máxima de subarreglo = -3
[-2, 7, 1, -1]: suma máxima de subarreglo = 7 + 1 = 8
[4, 0, 5]: suma máxima de subarreglo = 4 + 0 + 5 = 9
[-4, 6]: suma máxima de subarreglo = 6
Entonces, suma máxima de subarreglo contiguo = 9
Enfoque: la idea es utilizar el recorrido transversal de búsqueda en profundidad para realizar un seguimiento de los componentes conectados en el gráfico no dirigido, como se explica en este artículo. Para cada componente conectado, se analiza la array y se calcula la suma máxima de subarreglos contiguos según el algoritmo de Kadane, como se explica en este artículo. Se establece una variable global que se compara en cada iteración con los valores de la suma local para obtener el resultado final.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
Maximum subarray sum among all connected components = 5
Complejidad de tiempo: O(V 2 )
El algoritmo DFS toma O(V + E) tiempo para ejecutarse, donde V, E son los vértices y bordes del gráfico no dirigido. Además, la suma máxima de subarreglo contiguo se encuentra en cada iteración que requiere un O(V) adicional para calcular y devolver el resultado según el algoritmo de Kadane. Por lo tanto, la complejidad global es O(V 2 )
Espacio auxiliar: O(V)
Publicación traducida automáticamente
Artículo escrito por PratikBasu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA