给定一个数组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