หาผลรวมมากที่สุดของคู่จากสอง Array ใน C++

ในปัญหานี้ เราได้รับ 2 arrays (ค่าบวก, ไม่ซ้ำ) งานคือหา ผลรวมมากที่สุดของคู่ที่เอา 1 ตัวจากแต่ละ array

ตัวอย่าง

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

คู่ (7, 8) ให้ผลรวม 15

วิธีที่ 1: Nested Loop O(N×M) - ไม่แนะนำ

วิธีที่ 2: หา Max ของแต่ละ Array O(N+M) (แนะนำ)

Max pair sum = Max(arr1) + Max(arr2)

int findMaxPairSum(int arr1[], int n1, int arr2[], int n2) {
    int max1 = *max_element(arr1, arr1 + n1);
    int max2 = *max_element(arr2, arr2 + n2);
    return max1 + max2;
}

วิธีที่ 3: Sort แล้วเอาตัวสุดท้าย O(N log N + M log M)

sort(arr1, arr1+n1); sort(arr2, arr2+n2);
return arr1[n1-1] + arr2[n2-1];

ตัวอย่างโค้ด (วิธีที่ 2)

#include <iostream>
#include <algorithm>
using namespace std;

int findMaxPairSum(int arr1[], int n1, int arr2[], int n2) {
    int max1 = -1, max2 = -1;
    for (int i = 0; i < n1; i++) max1 = max(max1, arr1[i]);
    for (int i = 0; i < n2; i++) max2 = max(max2, arr2[i]);
    return max1 + max2;
}

int main() {
    int arr1[] = {3, 7, 5}, arr2[] = {8, 2, 4};
    cout << findMaxPairSum(arr1, 3, arr2, 3); // 15
    return 0;
}

ผลลัพธ์

15