C++程序计算机领域最大平衡和

给定一个数组arr[]，找到索引i中前缀和和后缀和的最大值。

例子：

Input : arr[] = {-1, 2, 3, 0, 3, 2, -1}
Output : 4
arr[0..3]的前缀和 =
            arr[3..6]的后缀和

Input : arr[] = {-2, 5, 3, 1, 2, 6, -4, 2}
Output : 7
arr[0..3]的前缀和 = 
              arr[3..7]的后缀和

使用 简单解决方案 一个一个地检查每个元素是否满足给定条件（前缀和等于后缀和），并返回满足给定条件且具有最大值的元素。

// 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;
}

输出:

时间复杂度： O(n 2 )

辅助空间： O(n)

使用 更好的方法 遍历数组并将每个索引的前缀和存储在数组presum[]中，其中presum[i]存储子数组arr[0..i]的总和。对数组进行另一个遍历，并在另一个数组suffsum[]中存储后缀和，其中suffsum[i]存储子数组arr[i..n-1]的总和。此后，对于每个索引检查presum[i]是否等于suffsum[i]，如果它们相等，则将其值与迄今为止的最大值进行比较。

// 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;
}

输出:

时间复杂度： O(n)

辅助空间： O(n)

进一步优化：

我们可以通过首先计算总和，然后使用它来找到当前前缀和和后缀和来避免使用额外的空间。

// CPP程序来寻找
//最大平衡和。
#include <bits/stdc++.h>
使用名称空间std;
 
//函数来寻找
//最大平衡和。
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;
}
 
//驱动程序
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;
}

输出:

时间复杂度: O(n)

辅助空间: O(1)