หาผลคูณสูงสุดของ Quadruple (4 ตัว) ในอาร์เรย์ C++

หาผลคูณสูงสุดของ 4 ตัวเลข (Quadruple) ในอาร์เรย์

ตัวอย่าง: [3, 5, 20, 6, 10] → ผลคูณสูงสุด = 6000 (จาก 10, 5, 6, 20)

อัลกอริทึม

1. เรียงอาร์เรย์จากน้อยไปมาก
2. พิจารณา 3 กรณี:
   • ผลคูณ 4 ตัวท้าย (มากที่สุด)
   • ผลคูณ 4 ตัวหน้า (น้อยที่สุด - อาจเป็นลบ × ลบ = บวก)
   • ผลคูณ 2 ตัวหน้า × 2 ตัวท้าย (ลบ × ลบ × บวก × บวก)
3. เลือกค่าสูงสุดของทั้ง 3 กรณี

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

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

int maxQuadProduct(int arr[], int n) {
    if (n < 4) return -1;

    sort(arr, arr + n);

    int last_four = arr[n-1] * arr[n-2] * arr[n-3] * arr[n-4];
    int first_four = arr[0] * arr[1] * arr[2] * arr[3];
    int two_first_last = arr[0] * arr[1] * arr[n-1] * arr[n-2];

    return max(last_four, max(first_four, two_first_last));
}

int main() {
    int arr[] = {-10, -3, 5, 6, -20};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_val = maxQuadProduct(arr, n);

    if (max_val == -1)
        cout << "No Quadruple Exists";
    else
        cout << "Maximum product is " << max_val;

    return 0;
}

ผลลัพธ์

Maximum product is 6000

การตรวจสอบ

อาร์เรย์เรียง: [-20, -10, -3, 5, 6]

• Last 4: -10 × -3 × 5 × 6 = 900
• First 4: -20 × -10 × -3 × 5 = -3000
• First 2 × Last 2: -20 × -10 × 5 × 6 = 6000 ← สูงสุด

หมายเหตุ

ระวัง Integer Overflow สำหรับตัวเลขใหญ่ ควรใช้ long long