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.
C++
// CPP program to find
// maximum equilibrium sum.
#include <bits/stdc++.h>
using namespace std;
// Function to find
// maximum equilibrium sum.
int findMaxSum(int arr[], int n)
{
int res = INT_MIN;
for (int i = 0; i < n; i++)
{
int prefix_sum = arr[i];
for (int j = 0; j < i; j++)
prefix_sum += arr[j];
int suffix_sum = arr[i];
for (int j = n - 1; j > i; j--)
suffix_sum += arr[j];
if (prefix_sum == suffix_sum)
res = max(res, prefix_sum);
}
return res;
}
// Driver Code
int main()
{
int arr[] = {-2, 5, 3, 1,
2, 6, -4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMaxSum(arr, n);
return 0;
}
Java
// java program to find maximum
// equilibrium sum.
import java.io.*;
class GFG {
// Function to find maximum
// equilibrium sum.
static int findMaxSum(int []arr, int n)
{
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
{
int prefix_sum = arr[i];
for (int j = 0; j < i; j++)
prefix_sum += arr[j];
int suffix_sum = arr[i];
for (int j = n - 1; j > i; j--)
suffix_sum += arr[j];
if (prefix_sum == suffix_sum)
res = Math.max(res, prefix_sum);
}
return res;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {-2, 5, 3, 1, 2, 6, -4, 2 };
int n = arr.length;
System.out.println(findMaxSum(arr, n));
}
}
// This code is contributed by anuj_67.
Python3
# Python 3 program to find maximum # equilibrium sum. import sys # Function to find maximum equilibrium sum. def findMaxSum(arr, n): res = -sys.maxsize - 1 for i in range(n): prefix_sum = arr[i] for j in range(i): prefix_sum += arr[j] suffix_sum = arr[i] j = n - 1 while(j > i): suffix_sum += arr[j] j -= 1 if (prefix_sum == suffix_sum): res = max(res, prefix_sum) return res # Driver Code if __name__ == '__main__': arr = [-2, 5, 3, 1, 2, 6, -4, 2] n = len(arr) print(findMaxSum(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find maximum
// equilibrium sum.
using System;
class GFG {
// Function to find maximum
// equilibrium sum.
static int findMaxSum(int []arr, int n)
{
int res = int.MinValue;
for (int i = 0; i < n; i++)
{
int prefix_sum = arr[i];
for (int j = 0; j < i; j++)
prefix_sum += arr[j];
int suffix_sum = arr[i];
for (int j = n - 1; j > i; j--)
suffix_sum += arr[j];
if (prefix_sum == suffix_sum)
res = Math.Max(res, prefix_sum);
}
return res;
}
// Driver Code
public static void Main ()
{
int []arr = {-2, 5, 3, 1, 2, 6, -4, 2 };
int n = arr.Length;
Console.WriteLine(findMaxSum(arr, n));
}
}
// This code is contributed by anuj_67.
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.
?>
Javascript
<script>
// Javascript program to find
// maximum equilibrium sum.
// Function to find
// maximum equilibrium sum.
function findMaxSum(arr, n)
{
var res = -1000000000;
for (var i = 0; i < n; i++)
{
var prefix_sum = arr[i];
for (var j = 0; j < i; j++)
prefix_sum += arr[j];
var suffix_sum = arr[i];
for (var j = n - 1; j > i; j--)
suffix_sum += arr[j];
if (prefix_sum == suffix_sum)
res = Math.max(res, prefix_sum);
}
return res;
}
// Driver Code
var arr = [-2, 5, 3, 1,
2, 6, -4, 2 ];
var n = arr.length;
document.write( findMaxSum(arr, n));
</script>
Producción :
7
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n)
Un mejor enfoque es recorrer la array y almacenar la suma del prefijo 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.
C++
// CPP program to find
// maximum equilibrium sum.
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum
// equilibrium sum.
int findMaxSum(int arr[], int n)
{
// Array to store prefix sum.
int preSum[n];
// Array to store suffix sum.
int suffSum[n];
// Variable to store maximum sum.
int ans = INT_MIN;
// Calculate prefix sum.
preSum[0] = arr[0];
for (int i = 1; i < n; i++)
preSum[i] = preSum[i - 1] + arr[i];
// Calculate suffix sum and compare
// it with prefix sum. Update ans
// accordingly.
suffSum[n - 1] = arr[n - 1];
if (preSum[n - 1] == suffSum[n - 1])
ans = max(ans, preSum[n - 1]);
for (int i = n - 2; i >= 0; i--)
{
suffSum[i] = suffSum[i + 1] + arr[i];
if (suffSum[i] == preSum[i])
ans = max(ans, preSum[i]);
}
return ans;
}
// Driver Code
int main()
{
int arr[] = { -2, 5, 3, 1,
2, 6, -4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMaxSum(arr, n);
return 0;
}
Java
// Java program to find maximum equilibrium sum.
import java.io.*;
public class GFG {
// Function to find maximum
// equilibrium sum.
static int findMaxSum(int []arr, int n)
{
// Array to store prefix sum.
int []preSum = new int[n];
// Array to store suffix sum.
int []suffSum = new int[n];
// Variable to store maximum sum.
int ans = Integer.MIN_VALUE;
// Calculate prefix sum.
preSum[0] = arr[0];
for (int i = 1; i < n; i++)
preSum[i] = preSum[i - 1] + arr[i];
// Calculate suffix sum and compare
// it with prefix sum. Update ans
// accordingly.
suffSum[n - 1] = arr[n - 1];
if (preSum[n - 1] == suffSum[n - 1])
ans = Math.max(ans, preSum[n - 1]);
for (int i = n - 2; i >= 0; i--)
{
suffSum[i] = suffSum[i + 1] + arr[i];
if (suffSum[i] == preSum[i])
ans = Math.max(ans, preSum[i]);
}
return ans;
}
// Driver Code
static public void main (String[] args)
{
int []arr = { -2, 5, 3, 1, 2, 6, -4, 2 };
int n = arr.length;
System.out.println( findMaxSum(arr, n));
}
}
// This code is contributed by anuj_67
Python3
# Python3 program to find # maximum equilibrium sum. # Function to find maximum # equilibrium sum. def findMaxSum(arr, n): # Array to store prefix sum. preSum = [0 for i in range(n)] # Array to store suffix sum. suffSum = [0 for i in range(n)] # Variable to store maximum sum. ans = -10000000 # Calculate prefix sum. preSum[0] = arr[0] for i in range(1, n): preSum[i] = preSum[i - 1] + arr[i] # Calculate suffix sum and compare # it with prefix sum. Update ans # accordingly. suffSum[n - 1] = arr[n - 1] if (preSum[n - 1] == suffSum[n - 1]): ans = max(ans, preSum[n - 1]) for i in range(n - 2, -1, -1): suffSum[i] = suffSum[i + 1] + arr[i] if (suffSum[i] == preSum[i]): ans = max(ans, preSum[i]) return ans # Driver Code if __name__=='__main__': arr = [-2, 5, 3, 1,2, 6, -4, 2] n = len(arr) print(findMaxSum(arr, n)) # This code i contributed by pratham76
C#
// C# program to find maximum equilibrium sum.
using System;
public class GFG {
// Function to find maximum
// equilibrium sum.
static int findMaxSum(int []arr, int n)
{
// Array to store prefix sum.
int []preSum = new int[n];
// Array to store suffix sum.
int []suffSum = new int[n];
// Variable to store maximum sum.
int ans = int.MinValue;
// Calculate prefix sum.
preSum[0] = arr[0];
for (int i = 1; i < n; i++)
preSum[i] = preSum[i - 1] + arr[i];
// Calculate suffix sum and compare
// it with prefix sum. Update ans
// accordingly.
suffSum[n - 1] = arr[n - 1];
if (preSum[n - 1] == suffSum[n - 1])
ans = Math.Max(ans, preSum[n - 1]);
for (int i = n - 2; i >= 0; i--)
{
suffSum[i] = suffSum[i + 1] + arr[i];
if (suffSum[i] == preSum[i])
ans = Math.Max(ans, preSum[i]);
}
return ans;
}
// Driver Code
static public void Main ()
{
int []arr = { -2, 5, 3, 1, 2, 6, -4, 2 };
int n = arr.Length;
Console.WriteLine( findMaxSum(arr, n));
}
}
// This code is contributed by anuj_67
PHP
<?php
// PHP program to find maximum equilibrium sum.
// Function to find maximum equilibrium sum.
function findMaxSum($arr, $n)
{
// Array to store prefix sum.
$preSum[$n] = array();
// Array to store suffix sum.
$suffSum[$n] = array();
// Variable to store maximum sum.
$ans = PHP_INT_MIN;
// Calculate prefix sum.
$preSum[0] = $arr[0];
for ($i = 1; $i < $n; $i++)
$preSum[$i] = $preSum[$i - 1] + $arr[$i];
// Calculate suffix sum and compare
// it with prefix sum. Update ans
// accordingly.
$suffSum[$n - 1] = $arr[$n - 1];
if ($preSum[$n - 1] == $suffSum[$n - 1])
$ans = max($ans, $preSum[$n - 1]);
for ($i = $n - 2; $i >= 0; $i--)
{
$suffSum[$i] = $suffSum[$i + 1] + $arr[$i];
if ($suffSum[$i] == $preSum[$i])
$ans = max($ans, $preSum[$i]);
}
return $ans;
}
// Driver Code
$arr = array( -2, 5, 3, 1, 2, 6, -4, 2 );
$n = sizeof($arr);
echo findMaxSum($arr, $n);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to find
// maximum equilibrium sum.
// Function to find maximum
// equilibrium sum.
function findMaxSum(arr, n)
{
// Array to store prefix sum.
let preSum = new Array(n);
preSum.fill(0);
// Array to store suffix sum.
let suffSum = new Array(n);
suffSum.fill(0);
// Variable to store maximum sum.
let ans = Number.MIN_VALUE;
// Calculate prefix sum.
preSum[0] = arr[0];
for(let i = 1; i < n; i++)
preSum[i] = preSum[i - 1] + arr[i];
// Calculate suffix sum and compare
// it with prefix sum. Update ans
// accordingly.
suffSum[n - 1] = arr[n - 1];
if (preSum[n - 1] == suffSum[n - 1])
ans = Math.max(ans, preSum[n - 1]);
for(let i = n - 2; i >= 0; i--)
{
suffSum[i] = suffSum[i + 1] + arr[i];
if (suffSum[i] == preSum[i])
ans = Math.max(ans, preSum[i]);
}
return ans;
}
// Driver code
let arr = [ -2, 5, 3, 1, 2, 6, -4, 2 ];
let n = arr.length;
document.write(findMaxSum(arr, n));
// This code is contributed by rameshtravel07
</script>
Producción:
7
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Optimización adicional:
podemos evitar el uso de espacio adicional calculando primero la suma total y luego usándola para encontrar las sumas actuales de prefijos y sufijos.
C++
// CPP program to find
// maximum equilibrium sum.
#include <bits/stdc++.h>
using namespace std;
// Function to find
// maximum equilibrium sum.
int findMaxSum(int arr[], int n)
{
int sum = accumulate(arr, arr + n, 0);
int prefix_sum = 0, res = INT_MIN;
for (int i = 0; i < n; i++)
{
prefix_sum += arr[i];
if (prefix_sum == sum)
res = max(res, prefix_sum);
sum -= arr[i];
}
return res;
}
// Driver Code
int main()
{
int arr[] = { -2, 5, 3, 1,
2, 6, -4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMaxSum(arr, n);
return 0;
}
Java
// Java program to find maximum equilibrium
// sum.
import java.lang.Math.*;
import java.util.stream.*;
class GFG {
// Function to find maximum equilibrium
// sum.
static int findMaxSum(int arr[], int n)
{
int sum = IntStream.of(arr).sum();
int prefix_sum = 0,
res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
{
prefix_sum += arr[i];
if (prefix_sum == sum)
res = Math.max(res, prefix_sum);
sum -= arr[i];
}
return res;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { -2, 5, 3, 1,
2, 6, -4, 2 };
int n = arr.length;
System.out.print(findMaxSum(arr, n));
}
}
// This code is contributed by Smitha.
Python3
# Python3 program to find # maximum equilibrium sum. import sys # Function to find # maximum equilibrium sum. def findMaxSum(arr,n): ss = sum(arr) prefix_sum = 0 res = -sys.maxsize for i in range(n): prefix_sum += arr[i] if prefix_sum == ss: res = max(res, prefix_sum); ss -= arr[i]; return res # Driver code if __name__=="__main__": arr = [ -2, 5, 3, 1, 2, 6, -4, 2 ] n = len(arr) print(findMaxSum(arr, n)) # This code is contributed by rutvik_56
C#
// C# program to find maximum equilibrium sum.
using System.Linq;
using System;
class GFG {
static int Add(int x, int y) {
return x + y;
}
// Function to find maximum equilibrium
// sum.
static int findMaxSum(int []arr, int n)
{
int sum = arr.Aggregate(func:Add);
int prefix_sum = 0,
res = int.MinValue;
for (int i = 0; i < n; i++)
{
prefix_sum += arr[i];
if (prefix_sum == sum)
res = Math.Max(res, prefix_sum);
sum -= arr[i];
}
return res;
}
// Driver Code
public static void Main()
{
int []arr = { -2, 5, 3, 1,
2, 6, -4, 2 };
int n = arr.Length;
Console.Write(findMaxSum(arr, n));
}
}
// This code is contributed by Smitha.
Javascript
<script>
// javascript program to find
// maximum equilibrium sum.
// Function to find
// maximum equilibrium sum.
function findMaxSum(arr,n)
{
let sum = 0;
for(let i=0; i < n; i++)
{
sum = sum + arr[i];
}
let prefix_sum = 0, res = Number.MIN_VALUE;
for (let i = 0; i < n; i++)
{
prefix_sum += arr[i];
if (prefix_sum == sum)
res = Math.max(res, prefix_sum);
sum -= arr[i];
}
return res;
}
// Driver Code
let arr = [ -2, 5, 3, 1,
2, 6, -4, 2 ];
let n = arr.length;
document.write(findMaxSum(arr, n));
// This code is contributed by vaibhavrabadiya117.
</script>
Producción :
7
Complejidad temporal: O(n)
Espacio auxiliar: O(1)