Dados n números (tanto +ve como -ve), dispuestos en un círculo, encuentre la suma máxima de números consecutivos.
Ejemplos:
Input: a[] = {8, -8, 9, -9, 10, -11, 12} Output: 22 (12 + 8 - 8 + 9 - 9 + 10) Input: a[] = {10, -3, -4, 7, 6, 5, -4, -1} Output: 23 (7 + 6 + 5 - 4 -1 + 10) Input: a[] = {-1, 40, -14, 7, 6, 5, -4, -1} Output: 52 (7 + 6 + 5 - 4 - 1 - 1 + 40)
Método 1 Puede haber dos casos para la suma máxima:
- Caso 1: Los elementos que contribuyen a la suma máxima están dispuestos de manera que no haya envoltura. Ejemplos: {-10, 2, -1, 5}, {-2, 4, -1, 4, -1}. En este caso, el algoritmo de Kadane producirá el resultado.
- Caso 2: Los elementos que contribuyen a la suma máxima están dispuestos de tal manera que el envoltorio está ahí. Ejemplos: {10, -12, 11}, {12, -5, 4, -8, 11}. En este caso, cambiamos wrapping a non-wraping. Veamos cómo. Envolver los elementos contribuyentes implica no envolver los elementos no contribuyentes, así que averigüe la suma de los elementos no contribuyentes y reste esta suma de la suma total. Para averiguar la suma de las no contribuciones, invierta el signo de cada elemento y luego ejecute el algoritmo de Kadane.
Nuestro arreglo es como un anillo y tenemos que eliminar el máximo continuo negativo que implica el máximo continuo positivo en los arreglos invertidos. Finalmente, comparamos la suma obtenida en ambos casos y devolvemos el máximo de las dos sumas.
Las siguientes son implementaciones del método anterior.
Python
# Python program for maximum contiguous circular sum problem # Standard Kadane's algorithm to find maximum subarray sum def kadane(a): n = len(a) max_so_far = 0 max_ending_here = 0 for i in range(0, n): max_ending_here = max_ending_here + a[i] if (max_ending_here < 0): max_ending_here = 0 if (max_so_far < max_ending_here): max_so_far = max_ending_here return max_so_far # The function returns maximum circular contiguous sum in # a[] def maxCircularSum(a): n = len(a) # Case 1: get the maximum sum using standard kadane's # algorithm max_kadane = kadane(a) # Case 2: Now find the maximum sum that includes corner # elements. max_wrap = 0 for i in range(0, n): max_wrap += a[i] a[i] = -a[i] # Max sum with corner elements will be: # array-sum - (-max subarray sum of inverted array) max_wrap = max_wrap + kadane(a) # The maximum circular sum will be maximum of two sums if max_wrap > max_kadane: return max_wrap else: return max_kadane # Driver function to test above function a = [11, 10, -20, 5, -3, -5, 8, -13, 10] print "Maximum circular sum is", maxCircularSum(a) # This code is contributed by Devesh Agrawal
Producción:
Maximum circular sum is 31
Análisis de Complejidad:
- Complejidad de tiempo: O(n), donde n es el número de elementos en la array de entrada.
Como solo se necesita un recorrido lineal de la array. - Espacio Auxiliar: O(1).
Como no se requiere espacio adicional.
Tenga en cuenta que el algoritmo anterior no funciona si todos los números son negativos, por ejemplo, {-1, -2, -3}. Devuelve 0 en este caso. Este caso se puede manejar agregando una verificación previa para ver si todos los números son negativos antes de ejecutar el algoritmo anterior.
Método 2
Enfoque: en este método, modifique el algoritmo de Kadane para encontrar una suma mínima de subarreglo contiguo y la suma máxima de subarreglo contiguo, luego verifique el valor máximo entre max_value y el valor que queda después de restar min_value de la suma total.
Algoritmo
- Calcularemos la suma total de la array dada.
- Declararemos la variable curr_max, max_so_far, curr_min, min_so_far como el primer valor de la array.
- Ahora usaremos el Algoritmo de Kadane para encontrar la suma máxima del subarreglo y la suma mínima del subarreglo.
- Verifique todos los valores en la array: –
- Si min_so_far se iguala a sum, es decir, todos los valores son negativos, entonces devolvemos max_so_far.
- De lo contrario, calcularemos el valor máximo de max_so_far y (sum – min_so_far) y lo devolveremos.
La implementación del método anterior se da a continuación.
Python
# Python program for maximum contiguous circular sum problem # The function returns maximum # circular contiguous sum in a[] def maxCircularSum(a, n): # Corner Case if (n == 1): return a[0] # Initialize sum variable which # store total sum of the array. sum = 0 for i in range(n): sum += a[i] # Initialize every variable # with first value of array. curr_max = a[0] max_so_far = a[0] curr_min = a[0] min_so_far = a[0] # Concept of Kadane's Algorithm for i in range(1, n): # Kadane's Algorithm to find Maximum subarray sum. curr_max = max(curr_max + a[i], a[i]) max_so_far = max(max_so_far, curr_max) # Kadane's Algorithm to find Minimum subarray sum. curr_min = min(curr_min + a[i], a[i]) min_so_far = min(min_so_far, curr_min) if (min_so_far == sum): return max_so_far # returning the maximum value return max(max_so_far, sum - min_so_far) # Driver code a = [11, 10, -20, 5, -3, -5, 8, -13, 10] n = len(a) print("Maximum circular sum is", maxCircularSum(a, n)) # This code is contributes by subhammahato348
Producción:
Maximum circular sum is 31
Análisis de Complejidad:
- Complejidad de tiempo: O(n), donde n es el número de elementos en la array de entrada.
Como solo se necesita un recorrido lineal de la array. - Espacio Auxiliar: O(1).
Como no se requiere espacio adicional.
Consulte el artículo completo sobre la suma máxima de subarreglo circular para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA