Tìm tổng cặp lớn nhất từ hai mảng C++

Cho hai mảng số nguyên dương, phân biệt. Nhiệm vụ: tìm tổng lớn nhất của cặp (một phần tử từ mỗi mảng).

Ví dụ minh họa

Input: arr1[] = {3, 7, 5}, arr2[] = {8, 2, 4} Output: 15

Cặp (7, 8) cho tổng 15.

Phương pháp 1: Tìm max từng mảng O(n₁+n₂)

Duyệt từng mảng tìm max, cộng hai max.

Phương pháp 2: Sắp xếp O(n log n)

Sort cả hai mảng, lấy phần tử cuối của mỗi mảng.

Ví dụ chương trình (Phương pháp 1)

#include <iostream> 
using namespace std; 

int findMaxPairSum(int arr1[], int n1, int arr2[], int n2) {
    int max1 = INT_MIN, max2 = INT_MIN;
    for (int i = 0; i < n1; i++) if (arr1[i] > max1) max1 = arr1[i];
    for (int i = 0; i < n2; i++) if (arr2[i] > max2) max2 = arr2[i];
    return max1 + max2;
}

int main() {
    int arr1[] = {3, 7, 5};
    int arr2[] = {8, 2, 4};
    int n1 = sizeof(arr1)/sizeof(arr1[0]);
    int n2 = sizeof(arr2)/sizeof(arr2[0]);
    cout << "Tổng cặp lớn nhất: " << findMaxPairSum(arr1, n1, arr2, n2);
    return 0;
}

Kết quả

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