สมมติว่าเรามีอาร์เรย์จำนวนเต็มหนึ่งอาร์เรย์ที่มีองค์ประกอบ n ตัว เราต้องหาผลคูณสูงสุดของสี่เท่าในอาร์เรย์ ดังนั้นหากอาร์เรย์เป็นแบบ [3, 5, 20, 6, 10] ผลคูณสุดท้ายคือ 6000 และองค์ประกอบในสี่เท่าคือ 10, 5, 6, 20
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เรียงลำดับอาร์เรย์จากน้อยไปมาก
- สมมติว่า x เป็นผลคูณขององค์ประกอบสี่ตัวสุดท้าย y เป็นผลคูณขององค์ประกอบสี่ตัวแรก และ z เป็นผลคูณขององค์ประกอบสองตัวแรกและสององค์ประกอบที่สอง
- คืนค่าสูงสุดของ x, y และ z
ตัวอย่าง
#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 maximum_val = maxQuadProduct(arr, n);
if (maximum_val == -1)
cout << "No Quadruple Exists";
else
cout << "Maximum product is " << maximum_val;
} ผลลัพธ์
Maximum product is 6000
