Programa Php para la suma máxima de equilibrio en una array

Dada una array arr[]. Encuentre el valor máximo de la suma del prefijo que también es la suma del sufijo para el índice i en arr[].

Ejemplos: 

Input : arr[] = {-1, 2, 3, 0, 3, 2, -1}
Output : 4
Prefix sum of arr[0..3] = 
            Suffix sum of arr[3..6]

Input : arr[] = {-2, 5, 3, 1, 2, 6, -4, 2}
Output : 7
Prefix sum of arr[0..3] = 
              Suffix sum of arr[3..7]

Una solución simple es verificar una por una la condición dada (la suma del prefijo es igual a la suma del sufijo) para cada elemento y devuelve el elemento que satisface la condición dada con el valor máximo. 

PHP

<?php
// PHP program to find
// maximum equilibrium sum.
 
// Function to find
// maximum equilibrium sum.
function findMaxSum( $arr, $n)
{
    $res = PHP_INT_MIN;
    for ( $i = 0; $i < $n; $i++)
    {
    $prefix_sum = $arr[$i];
    for ( $j = 0; $j < $i; $j++)
        $prefix_sum += $arr[$j];
 
    $suffix_sum = $arr[$i];
    for ( $j = $n - 1; $j > $i; $j--)
        $suffix_sum += $arr[$j];
 
    if ($prefix_sum == $suffix_sum)
        $res = max($res, $prefix_sum);
    }
    return $res;
}
 
// Driver Code
$arr = array(-2, 5, 3, 1,
              2, 6, -4, 2 );
$n = count($arr);
echo findMaxSum($arr, $n);
 
// This code is contributed by anuj_67.
?>
Producción : 

7

 

Complejidad de Tiempo: O(n 2
Espacio Auxiliar: O(n)

Un mejor enfoque es recorrer la array y almacenar la suma de prefijos para cada índice en la array presum[], en la que presum[i] almacena la suma de la subarreglo arr[0..i]. Realice otro recorrido de la array y almacene el sufijo sum en otra array suffsum[], en la que suffsum[i] almacena la suma de subarreglo arr[i..n-1]. Después de esto, para cada índice, compruebe si presum[i] es igual a suffsum[i] y, si son iguales, compare su valor con el máximo general hasta el momento.

Producción: 

7

 

Complejidad temporal: O(n) 
Espacio auxiliar: O(n)

Consulte el artículo completo sobre la suma máxima de equilibrio en una array 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *