Tìm cặp có tổng lớn nhất trong mảng không sắp xếp C++

Cho mảng arr[] N phần tử không sắp xếp. Nhiệm vụ: tìm cặp có tổng lớn nhất.

Ví dụ minh họa

Input: arr[] = {7, 3, 9, 12, 1} Output: 21

Cặp (9, 12) cho tổng 21.

Phương pháp giải

Tìm max và secondMax trong một lần duyệt. Khởi tạo từ 2 phần tử đầu, cập nhật khi duyệt từ chỉ số 2.

Ví dụ chương trình

#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 << "Tổng cặp lớn nhất: " << findPairLargestSum(arr, n);
    return 0;
}

Kết quả

Tổng cặp lớn nhất: 74