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