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.
Gracias a ashishdey0 por sugerir esta solución.
Implementación: Las siguientes son implementaciones del método anterior.
C++
// C++ program for maximum contiguous circular sum problem
#include <bits/stdc++.h>
#include <climits>
using namespace std;
// Standard Kadane's algorithm to
// find maximum subarray sum
int kadane(int a[], int n);
// The function returns maximum
// circular contiguous sum in a[]
int maxCircularSum(int a[], int n)
{
// Case 1: get the maximum sum using standard kadane'
// s algorithm
int max_kadane = kadane(a, n);
// if maximum sum using standard kadane' is less than 0
if(max_kadane < 0)
return max_kadane;
// Case 2: Now find the maximum sum that includes
// corner elements.
int max_wrap = 0, i;
for (i = 0; i < n; i++) {
max_wrap += a[i]; // Calculate array-sum
a[i] = -a[i]; // invert the array (change sign)
}
// max sum with corner elements will be:
// array-sum - (-max subarray sum of inverted array)
max_wrap = max_wrap + kadane(a, n);
// The maximum circular sum will be maximum of two sums
return (max_wrap > max_kadane) ? max_wrap : max_kadane;
}
// Standard Kadane's algorithm to find maximum subarray sum
// See https:// www.geeksforgeeks.org/archives/576 for details
int kadane(int a[], int n)
{
int max_so_far = INT_MIN, max_ending_here = 0;
int i;
for (i = 0; i < n; i++) {
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
/* Driver program to test maxCircularSum() */
int main()
{
int a[] = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };
int n = sizeof(a) / sizeof(a[0]);
cout << "Maximum circular sum is " << maxCircularSum(a, n) << endl;
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program for maximum contiguous circular sum problem
#include <stdio.h>
// Standard Kadane's algorithm to find maximum subarray
// sum
int kadane(int a[], int n);
// The function returns maximum circular contiguous sum
// in a[]
int maxCircularSum(int a[], int n)
{
// Case 1: get the maximum sum using standard kadane'
// s algorithm
int max_kadane = kadane(a, n);
// Case 2: Now find the maximum sum that includes
// corner elements.
int max_wrap = 0, i;
for (i = 0; i < n; i++) {
max_wrap += a[i]; // Calculate array-sum
a[i] = -a[i]; // invert the array (change sign)
}
// max sum with corner elements will be:
// array-sum - (-max subarray sum of inverted array)
max_wrap = max_wrap + kadane(a, n);
// The maximum circular sum will be maximum of two sums
return (max_wrap > max_kadane) ? max_wrap : max_kadane;
}
// Standard Kadane's algorithm to find maximum subarray sum
// See https:// www.geeksforgeeks.org/archives/576 for details
int kadane(int a[], int n)
{
int max_so_far = 0, max_ending_here = 0;
int i;
for (i = 0; i < n; i++) {
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;
}
/* Driver program to test maxCircularSum() */
int main()
{
int a[] = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };
int n = sizeof(a) / sizeof(a[0]);
printf("Maximum circular sum is %dn",
maxCircularSum(a, n));
return 0;
}
Java
// Java program for maximum contiguous circular sum problem
import java.io.*;
import java.util.*;
class Solution{
public static int kadane(int a[],int n){
int res = 0;
int x = a[0];
for(int i = 0; i < n; i++){
res = Math.max(a[i],res+a[i]);
x= Math.max(x,res);
}
return x;
}
//lets write a function for calculating max sum in circular manner as discuss above
public static int reverseKadane(int a[],int n){
int total = 0;
//taking the total sum of the array elements
for(int i = 0; i< n; i++){
total +=a[i];
}
// inverting the array
for(int i = 0; i<n ; i++){
a[i] = -a[i];
}
// finding min sum subarray
int k = kadane(a,n);
// max circular sum
int ress = total+k;
// to handle the case in which all elements are negative
if(total == -k ){
return total;
}
else{
return ress;
}
}
public static void main(String[] args)
{ int a[] = {1,4,6,4,-3,8,-1};
int n = 7;
if(n==1){
System.out.println("Maximum circular sum is " +a[0]);
}
else{
System.out.println("Maximum circular sum is " +Integer.max(kadane(a,n), reverseKadane(a,n)));
}
}
} /* This code is contributed by Mohit Kumar*/
Python
# Python program for maximum contiguous circular sum problem # Standard Kadane's algorithm to find maximum subarray sum def kadane(a): Max = a[0] temp = Max for i in range(1,len(a)): temp += a[i] if temp < a[i]: temp = a[i] Max = max(Max,temp) return Max # 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. # You can do so by finding the maximum negative contiguous # sum # convert a to -ve 'a' and run kadane's algo neg_a = [-1*x for x in a] max_neg_kadane = kadane(neg_a) # Max sum with corner elements will be: # array-sum - (-max subarray sum of inverted array) max_wrap = -(sum(neg_a)-max_neg_kadane) # The maximum circular sum will be maximum of two sums res = max(max_wrap,max_kadane) return res if res != 0 else 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
C#
// C# program for maximum contiguous
// circular sum problem
using System;
class MaxCircularSum {
// The function returns maximum circular
// contiguous sum in a[]
static int maxCircularSum(int[] a)
{
int n = a.Length;
// Case 1: get the maximum sum using standard kadane'
// s algorithm
int max_kadane = kadane(a);
// Case 2: Now find the maximum sum that includes
// corner elements.
int max_wrap = 0;
for (int i = 0; i < n; i++) {
max_wrap += a[i]; // Calculate array-sum
a[i] = -a[i]; // invert the array (change sign)
}
// 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
return (max_wrap > max_kadane) ? max_wrap : max_kadane;
}
// Standard Kadane's algorithm to find maximum subarray sum
// See https:// www.geeksforgeeks.org/archives/576 for details
static int kadane(int[] a)
{
int n = a.Length;
int max_so_far = 0, max_ending_here = 0;
for (int i = 0; i < n; i++) {
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;
}
// Driver code
public static void Main()
{
int[] a = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };
Console.Write("Maximum circular sum is " + maxCircularSum(a));
}
}
/* This code is contributed by vt_m*/
PHP
<?php
// PHP program for maximum
// contiguous circular sum problem
// The function returns maximum
// circular contiguous sum $a[]
function maxCircularSum($a, $n)
{
// Case 1: get the maximum sum
// using standard kadane' s algorithm
$max_kadane = kadane($a, $n);
// Case 2: Now find the maximum
// sum that includes corner elements.
$max_wrap = 0;
for ($i = 0; $i < $n; $i++)
{
$max_wrap += $a[$i]; // Calculate array-sum
$a[$i] = -$a[$i]; // invert the array (change sign)
}
// max sum with corner elements will be:
// array-sum - (-max subarray sum of inverted array)
$max_wrap = $max_wrap + kadane($a, $n);
// The maximum circular sum will be maximum of two sums
return ($max_wrap > $max_kadane)? $max_wrap: $max_kadane;
}
// Standard Kadane's algorithm to
// find maximum subarray sum
// See https://www.geeksforgeeks.org/archives/576 for details
function kadane($a, $n)
{
$max_so_far = 0;
$max_ending_here = 0;
for ($i = 0; $i < $n; $i++)
{
$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;
}
/* Driver code */
$a = array(11, 10, -20, 5, -3, -5, 8, -13, 10);
$n = count($a);
echo "Maximum circular sum is ". maxCircularSum($a, $n);
// This code is contributed by rathbhupendra
?>
Javascript
<script>
// javascript program for maximum contiguous circular sum problem
function kadane(a , n) {
var res = 0;
var x = a[0];
for (i = 0; i < n; i++) {
res = Math.max(a[i], res + a[i]);
x = Math.max(x, res);
}
return x;
}
// lets write a function for calculating max sum in circular manner as discuss
// above
function reverseKadane(a , n) {
var total = 0;
// taking the total sum of the array elements
for (i = 0; i < n; i++) {
total += a[i];
}
// inverting the array
for (i = 0; i < n; i++) {
a[i] = -a[i];
}
// finding min sum subarray
var k = kadane(a, n);
// max circular sum
var ress = total + k;
// to handle the case in which all elements are negative
if (total == -k) {
return total;
}
else {
return ress;
}
}
var a = [11, 10, -20, 5, -3, -5, 8, -13, 10];
var n = 9;
if (n == 1) {
document.write("Maximum circular sum is " + a[0]);
}
else {
document.write("Maximum circular sum is "
+ Math.max(kadane(a, n), reverseKadane(a, n)));
}
// This code is contributed by todaysgaurav
</script>
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 o podemos inicializar max_so_far como INT_MIN, por lo que el algoritmo también funciona para todos los números negativos.
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.
Implementación: La implementación del método anterior se da a continuación.
C++
// C++ program for maximum contiguous circular sum problem
#include <bits/stdc++.h>
using namespace std;
// The function returns maximum
// circular contiguous sum in a[]
int maxCircularSum(int a[], int n)
{
// Corner Case
if (n == 1)
return a[0];
// Initialize sum variable which store total sum of the array.
int sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
// Initialize every variable with first value of array.
int curr_max = a[0], max_so_far = a[0], curr_min = a[0], min_so_far = a[0];
// Concept of Kadane's Algorithm
for (int i = 1; i < n; i++) {
// 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 program to test maxCircularSum() */
int main()
{
int a[] = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };
int n = sizeof(a) / sizeof(a[0]);
cout << "Maximum circular sum is " << maxCircularSum(a, n) << endl;
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static int maxCircularSum(int a[], int n)
{
// Corner Case
if (n == 1)
return a[0];
// Initialize sum variable which store total sum of
// the array.
int sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
// Initialize every variable with first value of
// array.
int curr_max = a[0], max_so_far = a[0],
curr_min = a[0], min_so_far = a[0];
// Concept of Kadane's Algorithm
for (int i = 1; i < n; i++)
{
// Kadane's Algorithm to find Maximum subarray
// sum.
curr_max = Math.max(curr_max + a[i], a[i]);
max_so_far = Math.max(max_so_far, curr_max);
// Kadane's Algorithm to find Minimum subarray
// sum.
curr_min = Math.min(curr_min + a[i], a[i]);
min_so_far = Math.min(min_so_far, curr_min);
}
if (min_so_far == sum) {
return max_so_far;
}
// returning the maximum value
return Math.max(max_so_far, sum - min_so_far);
}
// Driver code
public static void main(String[] args)
{
int a[] = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };
int n = 9;
System.out.println("Maximum circular sum is "
+ maxCircularSum(a, n));
}
}
// This code is contributed by aditya7409
Python3
# 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
C#
// C# program for maximum contiguous circular sum problem
using System;
class GFG
{
public static int maxCircularSum(int[] a, int n)
{
// Corner Case
if (n == 1)
return a[0];
// Initialize sum variable which store total sum of
// the array.
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += a[i];
}
// Initialize every variable with first value of
// array.
int curr_max = a[0], max_so_far = a[0],
curr_min = a[0], min_so_far = a[0];
// Concept of Kadane's Algorithm
for (int i = 1; i < n; i++)
{
// Kadane's Algorithm to find Maximum subarray
// sum.
curr_max = Math.Max(curr_max + a[i], a[i]);
max_so_far = Math.Max(max_so_far, curr_max);
// Kadane's Algorithm to find Minimum subarray
// sum.
curr_min = Math.Min(curr_min + a[i], a[i]);
min_so_far = Math.Min(min_so_far, curr_min);
}
if (min_so_far == sum)
{
return max_so_far;
}
// returning the maximum value
return Math.Max(max_so_far, sum - min_so_far);
}
// Driver code
public static void Main()
{
int[] a = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };
int n = 9;
Console.WriteLine("Maximum circular sum is "
+ maxCircularSum(a, n));
}
}
// This code is contributed by subhammahato348
Javascript
<script>
// JavaScript program for the above approach
// The function returns maximum
// circular contiguous sum in a[]
function maxCircularSum(a, n) {
// Corner Case
if (n == 1)
return a[0];
// Initialize sum variable which store total sum of the array.
let sum = 0;
for (let i = 0; i < n; i++) {
sum += a[i];
}
// Initialize every variable with first value of array.
let curr_max = a[0], max_so_far = a[0], curr_min = a[0], min_so_far = a[0];
// Concept of Kadane's Algorithm
for (let i = 1; i < n; i++) {
// Kadane's Algorithm to find Maximum subarray sum.
curr_max = Math.max(curr_max + a[i], a[i]);
max_so_far = Math.max(max_so_far, curr_max);
// Kadane's Algorithm to find Minimum subarray sum.
curr_min = Math.min(curr_min + a[i], a[i]);
min_so_far = Math.min(min_so_far, curr_min);
}
if (min_so_far == sum)
return max_so_far;
// returning the maximum value
return Math.max(max_so_far, sum - min_so_far);
}
// Driver program to test maxCircularSum()
let a = [11, 10, -20, 5, -3, -5, 8, -13, 10];
let n = a.length;
document.write("Maximum circular sum is " + maxCircularSum(a, n));
// This code is contributed by Potta Lokesh
</script>
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.
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