ในปัญหานี้ เราได้รับอาร์เรย์สองอาร์เรย์ arr1[] และ arr2[] ขนาด n งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดของสองอาร์เรย์
คำอธิบายปัญหา − เราจำเป็นต้องหาผลรวมสูงสุดของผลิตภัณฑ์ของสองอาร์เรย์ เราจำเป็นต้องหาผลรวมสูงสุดของผลคูณขององค์ประกอบหนึ่งจาก 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
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการค้นหาคู่ขององค์ประกอบทั้งหมด fromarr1 และ 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
