ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่มีค่าจำนวนเต็ม n ค่า (อนุญาตให้ใช้ค่าลบ) งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดของผลิตภัณฑ์แบบคู่ในอาร์เรย์ที่อนุญาตให้มีค่าลบ
คำอธิบายปัญหา − เราจำเป็นต้องสร้างคู่โดยใช้องค์ประกอบของอาร์เรย์เพื่อให้ผลรวมของผลิตภัณฑ์ขององค์ประกอบของคู่มีค่าสูงสุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {−5, 2, 3, 7, −1, 1, −3, 12} ผลลัพธ์
104
คำอธิบาย
The pairs to be considered: (−5, −3), (2, 3), (−1, 1), (7, 12) Sum of product = (−5 * −3) + (2 * 3) + (−1 * 1) + (7 * 12) = 15 + 6 − 1 + 84 = 104.
แนวทางการแก้ปัญหา
ในการแก้ปัญหา เราจะหาคู่ในลักษณะที่ผลรวมของผลิตภัณฑ์ของพวกเขาสูงสุด เพื่อให้ได้ผลรวมสูงสุด เราต้องจับคู่ค่าคู่เดียวกันเข้าด้วยกัน และทำให้การจับคู่นี้ง่ายขึ้น เราต้องเรียงลำดับอาร์เรย์แล้วจับคู่ค่าลบและค่าบวก จากนั้นให้หาว่ามีค่า ornegative บวกหรือทั้งสองค่าอยู่ในคู่หรือไม่ หากค่าบวก/ค่าลบยังคงอยู่ ให้เพิ่มลงในคู่เงิน และหากมีค่าลบหนึ่งค่าและค่าบวกหนึ่งค่า ให้เพิ่มผลคูณของค่านั้น
อัลกอริทึม
เริ่มต้น −
maxSum = 0.
ขั้นตอนที่ 1 −
Sort the array arr[].
ขั้นตอนที่ 2 −
Loop for all negative values of the array. Make pairs, and add their product to maxSum.
ขั้นตอนที่ 3 −
Loop for all positive values of the array. Make pairs, and add their product to maxSum.
ขั้นตอนที่ 4 −
At last check the remaining values.
ขั้นตอนที่ 4.1 −
If one positive value remains, add it to maxSum.
ขั้นตอนที่ 4.1 −
If one negative value remains, add it to maxSum.
ขั้นตอนที่ 4.1 −
If one positive value and one negative value remains, add their product to maxSum.
ขั้นตอนที่ 5 −
Return maxSum.
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
long calcSumPairProd(int arr[], int n) {
long maxSum = 0;
sort(arr, arr + n);
int i = 0, j = (n − 1);
while (i < n && arr[i] < 0) {
if (i != n − 1 && arr[i + 1] <= 0) {
maxSum = (maxSum + (arr[i] * arr[i + 1]) );
i += 2;
}
else
break;
}
while (j >= 0 && arr[j] > 0) {
if (j != 0 && arr[j − 1] > 0) {
maxSum = (maxSum + (arr[j] * arr[j − 1]) );
j −= 2;
}
else
break;
}
if (j > i)
maxSum = (maxSum + (arr[i] * arr[j]) );
else if (i == j)
maxSum = (maxSum + arr[i]);
return maxSum;
}
int main() {
int arr[] = { −5, 2, 3, 7, −1, 1, −3, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum of pairwise product in an array is "<<calcSumPairProd(arr, n);
return 0;
} ผลลัพธ์
The maximum sum of pairwise product in an array is 104
