Programa Javascript para la suma máxima de subarreglo circular

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. 

<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.

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 

1. Calcularemos la suma total de la array dada.
2. Declararemos la variable curr_max, max_so_far, curr_min, min_so_far como el primer valor de la array.
3. Ahora usaremos el Algoritmo de Kadane para encontrar la suma máxima del subarreglo y la suma mínima del subarreglo.
4. Verifique todos los valores en la array: – 
   1. Si min_so_far se iguala a sum, es decir, todos los valores son negativos, entonces devolvemos max_so_far.
   2. 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.  

<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.

Consulte el artículo completo sobre la suma máxima de subarreglo circular para obtener más detalles.