C++で配列を均等に分割するために必要な最小の正の整数

問題の説明

N個の正の整数の配列が与えられた場合、タスクは、配列の任意の2つの要素の間に配置できる最小の正の整数を見つけて、その前に発生するサブ配列内の要素の合計が、発生する要素の合計と等しくなるようにすることです。その後のサブ配列で、新しく配置された整数が2つのサブ配列のいずれかに含まれます

例

arr ={3、2、1、5、7、10}の場合、出力は6です。値6を5と7の間に置くと、左右のサブアレイの合計は次のように等しくなります-

+ 2 + 1 + 5 + 6 =17

7 + 10 =17

アルゴリズム

• 配列全体の合計をSで計算します
• アイデアは、インデックスi（それを含む）までの左の合計を見つけることです。この合計をLとします
• これで、サブ配列arri + 1 ..Nの合計はS–Lになります。この合計をRとします
• 2つのサブアレイの合計は等しいと想定されるため、上記で取得した2つの合計LとRの大きい方を、これら2つの合計の小さい方の値と、大きい方の合計と合計が小さいほど、必要な正の整数の値になります。

例

#include <iostream>
#include <numeric>
#include <climits>
using namespace std;
int getMinimumSplitPoint(int *arr, int n) {
   int sum = 0;
   sum = accumulate(arr, arr + n, sum);
   int leftSum = 0;
   int rightSum = 0;
   int minValue = INT_MAX;
   for (int i = 0; i < n - 1; ++i) {
      leftSum += arr[i]; rightSum = sum - leftSum;
      if (leftSum > rightSum) {
         int e = leftSum - rightSum;
         if (e < minValue) {
            minValue = e;
         }
      } else {
         int e = rightSum - leftSum;
         if (e < minValue) {
            minValue = e;
         }
      }
   }
   return minValue;
}
int main() {
   int arr[] = {3, 2, 1, 5, 7, 10};
   int n = sizeof(arr) / sizeof(arr[0]);
   int minValue = getMinimumSplitPoint(arr, n);
   cout << "Element " << minValue << " needs to be inserted\n";
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Element 6 needs to be inserted