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