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