ในปัญหานี้ เราได้รับ arr[] ซึ่งประกอบด้วยองค์ประกอบที่ไม่ได้เรียงลำดับ N งานของเราคือ หาผลรวมคู่ที่ใหญ่ที่สุดในอาร์เรย์ที่ไม่เรียงลำดับ .
เราจะหาคู่ที่มีผลรวมสูงสุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : arr[] = {7, 3, 9, 12, 1}
Output : 21 คำอธิบาย −
Pair with largest sum, (9, 12). Sum = 21
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการสร้างคู่ขององค์ประกอบสูงสุดและสูงสุดที่สองของอาร์เรย์
สำหรับสิ่งนี้ เราจะเริ่มต้นองค์ประกอบ max และ secondMax ของอาร์เรย์ด้วยองค์ประกอบที่หนึ่งและสองของอาร์เรย์ ค่าที่มากกว่าคือ max และอีกองค์ประกอบหนึ่งคือ secondMax
ตอนนี้ วนรอบอาร์เรย์จากดัชนี 2 ถึง (n-1) และเปรียบเทียบกับค่า max และ secondMax
ถ้า arr[i] มากกว่า max, secondMax =max และ max =arr[i].
ถ้า arr[i] มากกว่า secondMax, secondMax =arr[i].
และเมื่อสิ้นสุดลูป ให้คืนค่า (max + secondMax)
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include<iostream>
using namespace std;
int findPairLargestSum(int arr[], int n){
int max, secondMax;
if (arr[0] > arr[1]){
max = arr[0];
secondMax = arr[1];
}
else{
max = arr[1];
secondMax = arr[0];
}
for (int i = 2; i<n; i ++){
if (arr[i] > max){
secondMax = max;
max = arr[i];
}
else if (arr[i] > secondMax && arr[i] != max)
secondMax = arr[i];
}
return (max + secondMax);
}
int main(){
int arr[] = {12, 34, 10, 6, 40};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The sum of elements of pair with max sum is "<<findPairLargestSum(arr, n);
return 0;
} ผลลัพธ์
The sum of elements of pair with max sum is 74
