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

ในปัญหานี้ เราได้รับ unsorted array งานคือหา คู่ (pair) ที่มีผลรวมมากที่สุด

ตัวอย่าง

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

คู่ (9, 12) ให้ผลรวม 21

วิธีการแก้ปัญหา: หา max และ second max แค่ครั้งเดียว O(N)

1. Initialize max และ secondMax จาก arr[0], arr[1]
2. วนลูป i = 2 ถึง n-1 อัปเดต max, secondMax
3. คืนค่า max + secondMax

ตัวอย่างโค้ด

#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};
    cout << "Max pair sum: " << findPairLargestSum(arr, 5);
    return 0;
}

ผลลัพธ์

Max pair sum: 74

(จากคู่ 40 + 34)