Trong bài toán này, chúng ta được đưa ra một arr [] bao gồm N phần tử không được sắp xếp. Nhiệm vụ của chúng tôi là tìm tổng cặp lớn nhất trong một mảng chưa được sắp xếp .
Chúng tôi sẽ tìm một cặp có tổng là lớn nhất.
Hãy lấy một ví dụ để hiểu vấn đề,
Input : arr[] = {7, 3, 9, 12, 1}
Output : 21 Giải thích -
Pair with largest sum, (9, 12). Sum = 21
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ạo một cặp phần tử lớn nhất và lớn nhất thứ hai của mảng.
Đối với điều này, chúng tôi sẽ khởi tạo phần tử max và secondMax của mảng bằng phần tử đầu tiên và thứ hai của mảng, phần tử lớn hơn là max và phần tử còn lại là secondMax.
Bây giờ, lặp qua mảng từ chỉ số 2 đến (n-1). Và so sánh chúng với giá trị max và secondMax.
Nếu arr [i] lớn hơn max, secondMax =max và max =arr [i].
Nếu arr [i] lớn hơn secondMax, secondMax =arr [i].
Và ở cuối vòng lặp, trả về (max + secondMax).
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<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;
} Đầu ra
The sum of elements of pair with max sum is 74