Trong bài toán này, chúng ta được cung cấp hai mảng arr1 [] và arr2 [] có kích thước n. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm Tổng các Sản phẩm tối đa của Hai Mảng.
Mô tả sự cố - Ta cần tìm tổng lớn nhất các tích của hai mảng. Chúng ta cần tìm tổng lớn nhất của tích của một phần tử từ arr1 và các phần tử khác từ arr2.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr1[] = {3, 5, 6} arr2[] = {1, 4, 2} Đầu ra
37
Giải thích
Maximum sum of products: 6*4 + 5*2 + 3*1 = 24 + 10 + 3 = 37
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm tất cả các cặp phần tử fromarr1 và arr2. Và sau đó trả về tổng tối đa.
Một giải pháp hiệu quả cho vấn đề là nhân các giá trị lớn nhất từ các mảng với nhau. Một cách dễ dàng để làm điều này là sắp xếp mảng theo thứ tự giảm dần. Sau đó, nhân tất cả các phần tử cho cả hai mảng với chỉ số 0 ton và trả về tổng của chúng.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum Sum of Products of two arrays is 37