C ++で繰り返し減算してすべての要素を同じにした後、最大配列合計を見つけます

n個の要素の配列があるとします。すべての要素が同じになるように、すべての要素の可能な最大合計を見つけます。許可される操作は、任意の2つの要素を選択し、それらの大きい方を2つの絶対差で置き換えることだけです。要素が[9、12、3、6]のようなものだとします。その場合、出力は12になります。したがって、最初にA[1]をA[1] – A [3] =12 – 6 =6に置き換えます。したがって、要素は[9、6、3、6]になり、次にA[を置き換えます。 3] with A [3] – A [2] =6 – 3 =3。したがって、要素は[9、6、3、3]です。次に、A[0]をA[0] – A [1] =9 – 6 =3に置き換えます。したがって、要素は[3、6、3、3]になります。最後に、A[1]をA[1] – A [3] =6 – 3 =3に置き換えます。したがって、要素は[3、3、3、3]です。つまり、すべて同じです。そして合計は12です

操作を分析すると、A [i] =A [i] – A [j]になります。ここで、A [i]>A[j]です。したがって、2つの数値を取得し、大きい方の値をそれらの絶対差で置き換えます。次に、すべてが同じになるまでこれらの手順を繰り返します。

例

#include<iostream>
#include<algorithm>
using namespace std;
int findSameElement(int arr[], int n) {
   int gcd_val = arr[0];
   for (int i = 1; i < n; i++)
   gcd_val = __gcd(arr[i], gcd_val);
   return gcd_val;
}
int getMaxSum(int arr[], int n) {
   int value = findSameElement(arr, n);
   return (value * n);
}
int main() {
   int arr[] = {3, 9, 6, 6};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "The maximum sum is: " << getMaxSum(arr, n);
}

出力

The maximum sum is: 12