ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม n ตัวและตัวเลข d หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดของคู่ที่มีความแตกต่างใน c++ .
คำอธิบายปัญหา − เราจะหาคู่ในลักษณะที่ความแตกต่างขององค์ประกอบของคู่มีค่าน้อยกว่า d ผลรวมของคู่ดังกล่าวทั้งหมดควรสูงสุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {5, 9, 11, 7, 2, 12, 3} d = 5 ผลลัพธ์
47
คำอธิบาย
Pairs that contribute to maximum sum: (3, 5), (7, 9), (11, 12). Sum = 3 + 5 + 7 + 9 + 11 + 12 = 47
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาที่ง่ายและชัดเจนคือการสร้างคู่ของอาร์เรย์ที่ถูกต้องทั้งหมด จากนั้นค้นหาผลรวมและส่งกลับค่าสูงสุดของผลรวมทั้งหมด แต่วิธีนี้ไม่มีประสิทธิภาพ
วิธีแก้ปัญหาที่มีประสิทธิภาพคือการใช้แนวทางการเขียนโปรแกรมแบบไดนามิก ที่นี่ เราจะหาคู่ที่เหมาะสมที่สุดที่ประกอบด้วยผลรวมสูงสุด สำหรับสิ่งนี้เราจะใช้อาร์เรย์ที่เรียงลำดับ ดังนั้นก่อนอื่น เราจะเรียงลำดับให้อาร์เรย์ แล้วดำเนินการกับมัน ในการค้นหาผลรวม เราจะใช้อาร์เรย์เพื่อเก็บผลรวมสูงสุดของคู่จนถึงองค์ประกอบปัจจุบัน สำหรับสิ่งนี้ เราจะตรวจสอบว่าองค์ประกอบปัจจุบันและองค์ประกอบก่อนหน้าสร้างคู่หรือไม่ ถ้าใช่ เราจะเพิ่มผลรวมของคู่ไปยัง maxSum จนถึงอาร์เรย์ มิฉะนั้น maxsum จะยังคงเหมือนเดิม
อัลกอริทึม
Initialize: DP[n]
ขั้นตอนที่ 1 −
For array arr[].
ขั้นตอนที่ 2
DP[0] = 0;
ขั้นตอนที่ 3 −
loop for i −> 1 to n
ขั้นตอนที่ 3.1 −
check if pairs with the previous element is possible. if(arr[i] − arr[i−1] < d).
ขั้นตอนที่ 3.2 −
if Yes, check if the current pair sum results in a greater value than the last considered sum and add the maximum value to the current sum. i.e. if( (DP[i−2] + arr[i−1] + arr[i]) > (DP[i−1])) −> DP[i] = (DP[i−2] + arr[i−1] + arr[i]), else −> DP[i] = DP[i−1].
ขั้นตอนที่ 3.3 −
an exception is for value i = 1, where no value of DP[i−2] is possible, in this case, DP[i−2] is not considered as it is the first pair sum.
ขั้นตอนที่ 4 −
Return DP[n−1].
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
int CalcmaxPairSum(int arr[], int n, int d) {
sort(arr, arr+n);
int maxSumDP[n];
maxSumDP[0] = 0;
for (int i = 1; i < n; i++) {
maxSumDP[i] = maxSumDP[i−1];
if (arr[i] − arr[i−1] < d) {
if (i >= 2)
if(maxSumDP[i] < (maxSumDP[i−2] + arr[i−1] +
arr[i]))
maxSumDP[i] = (maxSumDP[i−2] + arr[i−1] +
arr[i]);
else
if(maxSumDP[i] < (arr[i−1] + arr[i]))
maxSumDP[i] = arr[i−1] + arr[i];
}
}
return maxSumDP[n−1];
}
int main() {
int arr[] = {5, 9, 11, 7, 2, 12, 3};
int n = 7, d = 5;
cout<<"The maximum sum of pairs with specific difference is "<<CalcmaxPairSum(arr, n, d);
return 0;
} ผลลัพธ์
The maximum sum of pairs with specific difference is 47
