Programa Php 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)

Enfoque M: 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. 

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

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.

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