หาคู่ตัวเลขที่ให้ผลคูณมากที่สุดในอาร์เรย์จำนวนเต็ม C++

ปัญหา

ให้อาร์เรย์ A ที่มี n สมาชิก ต้องการหาคู่ (x, y) ที่ให้ผลคูณ x*y มากที่สุด อาร์เรย์อาจมีทั้งจำนวนบวกและลบ

ตัวอย่าง: A = [-1, -4, -3, 0, 2, -5] คู่ที่ให้ผลคูณมากที่สุดคือ (-4, -5) เพราะ -4 × -5 = 20

วิธีแก้ปัญหา

ติดตามค่า 4 ตัวสำคัญ:

• positive_max: ค่าบวกมากที่สุด
• positive_second_max: ค่าบวกมากเป็นอันดับสอง
• negative_max: ค่าลบที่มีค่าสัมบูรณ์มากที่สุด (เช่น -5)
• negative_second_max: ค่าลบที่มีค่าสัมบูรณ์มากเป็นอันดับสอง

ในที่สุด เปรียบเทียบ (positive_max × positive_second_max) กับ (negative_max × negative_second_max) คู่ที่ให้ผลคูณมากกว่าคือคำตอบ

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

#include <iostream>
#include <climits>
#include <cmath>
using namespace std;

void maxProdPair(int arr[], int n) {
    if (n < 2) {
        cout << "No pair is present";
        return;
    }
    if (n == 2) {
        cout << "(" << arr[0] << ", " << arr[1] << ")" << endl;
        return;
    }
    
    int pos_max = INT_MIN, pos_second_max = INT_MIN;
    int neg_max = INT_MIN, neg_second_max = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        // อัปเดตค่าบวก
        if (arr[i] > pos_max) {
            pos_second_max = pos_max;
            pos_max = arr[i];
        } else if (arr[i] > pos_second_max) {
            pos_second_max = arr[i];
        }
        
        // อัปเดตค่าลบ (พิจารณาจากค่าสัมบูรณ์)
        if (arr[i] < 0 && abs(arr[i]) > abs(neg_max)) {
            neg_second_max = neg_max;
            neg_max = arr[i];
        } else if (arr[i] < 0 && abs(arr[i]) > abs(neg_second_max)) {
            neg_second_max = arr[i];
        }
    }
    
    if (neg_max * neg_second_max > pos_max * pos_second_max)
        cout << "(" << neg_max << ", " << neg_second_max << ")" << endl;
    else
        cout << "(" << pos_max << ", " << pos_second_max << ")" << endl;
}

int main() {
    int arr[] = {-1, -4, -3, 0, 2, -5};
    int n = sizeof(arr)/sizeof(arr[0]);
    maxProdPair(arr, n);
    return 0;
}

ผลลัพธ์

(-5, -4)