Số cặp có tổng lớn nhất trong mảng C++

Cho mảng, tìm số cặp có tổng lớn nhất.

Ví dụ: arr = [3, 6, 5, 2, 1, 2, 3, 4, 1, 5]. Tổng lớn nhất = 10. Có 2 cặp: (5,5) và (6,4).

Giải thuật

• Khởi tạo maxSum = INT_MIN
• Hai vòng lặp lồng nhau tìm maxSum của mọi cặp
• Khởi tạo count = 0
• Hai vòng lặp lại: nếu a[i]+a[j] == maxSum thì count++
• Trả về count

Ví dụ minh họa

#include <bits/stdc++.h> 
using namespace std; 

int getMaxSumPairsCount(int a[], int n) { 
    int maxSum = INT_MIN; 
    for (int i = 0; i < n; i++) { 
        for (int j = i + 1; j < n; j++) { 
            maxSum = max(maxSum, a[i] + a[j]); 
        } 
    } 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
        for (int j = i + 1; j < n; j++) { 
            if (a[i] + a[j] == maxSum) { count++; } 
        } 
    } 
    return count; 
} 

int main() { 
    int arr[] = { 3, 4, 5, 2, 1, 2, 3, 4, 1, 5 }; 
    int n = 10; 
    cout << getMaxSumPairsCount(arr, n) << endl; 
    return 0; 
} 

Đầu ra

1