C++プログラムの2つの配列の積の最大合計

この問題では、サイズnの2つの配列arr1[]とarr2[]が与えられます。私たちのタスクは、2つの配列の積の最大合計を見つけるプログラムを作成することです。

問題の説明 −2つの配列の積の最大合計を見つける必要があります。 arr1の1つの要素とarr2のその他の要素の積の最大合計を見つける必要があります。

問題を理解するために例を見てみましょう

入力

arr1[] = {3, 5, 6} arr2[] = {1, 4, 2}

出力

37

説明

Maximum sum of products: 6*4 + 5*2 + 3*1 = 24 + 10 + 3 = 37

ソリューションアプローチ

この問題の簡単な解決策は、arr1とarr2の要素のすべてのペアを見つけることです。そして、最大合計を返します。

この問題の効率的な解決策は、両方の配列の最大値を乗算することです。これを行う簡単な方法は、配列を降順で並べ替えることです。次に、両方の配列のすべての要素をインデックス0トンから乗算し、それらの合計を返します。

例

ソリューションの動作を説明するプログラム

#include<bits/stdc++.h>
using namespace std;
int calcMaxSumOfProd(int arr1[], int arr2[], int n){
   int maxSum = 0;
   sort(arr1, arr1 + n, greater<int>());
   sort(arr2, arr2 + n, greater<int>());
   for (int i = 0; i < n; i++)
   maxSum += (arr1[i] * arr2[i]);
   return maxSum;
}
int main() {
   int arr1[] = { 3, 5, 6 };
   int arr2[] = { 1, 4, 2 };
   int n = sizeof(arr1)/sizeof(arr1[0]);
   cout<<"The maximum Sum of Products of two arrays is "<<calcMaxSumOfProd(arr1, arr2, n);
   return 0;
}

出力

The maximum Sum of Products of two arrays is 37