C++ 프로그램에서 두 배열의 곱의 최대 합

이 문제에서는 크기가 n인 두 개의 배열 arr1[] 및 arr2[]가 제공됩니다. 우리의 임무는 두 배열의 곱의 최대 합을 찾는 프로그램을 만드는 것입니다.

문제 설명 − 두 배열의 곱의 최대 합을 찾아야 합니다. arr1에서 한 요소와 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 ton에서 두 배열의 모든 요소를 ​​곱하고 합계를 반환합니다.

예시

우리 솔루션의 작동을 설명하는 프로그램

#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