C ++中数组的最大平衡总和
问题陈述
给定一个数组arr[]。在arr[]中找到前缀和的最大值，该最大值也是索引i的后缀和。
示例
如果输入数组是-
Arr[]={1,2,3,5,3,2,1}，则输出为11，-
前缀和=arr[0..3]=1+2+3+5=11且
后缀和=arr[3..6]=5+3+2+1=11
算法
遍历数组并将每个索引的前缀和存储在数组presum[]中，其中presum[i]存储子数组arr[0..i]的和
再次遍历数组并将后缀和存储在另一个数组suffsum[]中，其中suffsum[i]存储子数组arr[i..n-1]的和
对于每个索引，检查presum[i]是否等于suffsum[i]，如果相等，则进行比较，得出到目前为止的总最大值
示例
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
int preSum[n];
int suffSum[n];
int result = INT_MIN;
preSum[0] = arr[0];
for (int i = 1; i < n; ++i) {
preSum[i] = preSum[i - 1] + arr[i];
}
suffSum[n - 1] = arr[n - 1];
if (preSum[n - 1] == suffSum[n - 1]) {
result = max(result, preSum[n - 1]);
}
for (int i = n - 2; i >= 0; --i) {
suffSum[i] = suffSum[i + 1] + arr[i];
if (suffSum[i] == preSum[i]) {
result = max(result, preSum[i]);
}
}
return result;
}
int main() {
int arr[] = {1, 2, 3, 5, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max equlibrium sum = " << getMaxSum(arr, n) << endl;
return 0;
}输出结果
当您编译并执行上述程序时。它产生以下输出-
Max equlibrium sum = 11