Tích lớn nhất bộ 4 phần tử (tứ phần tử) trong mảng C++

Mô tả bài toán

Cho mảng, tìm 4 phần tử (không cần liên tiếp) có tích lớn nhất.

Ví dụ: {4, -2, 5, -6, 8} → Max = 480 (từ 4, 5, -6, -2 hoặc 8, 5, 4, -2...).

Giải pháp 1: Vét cạn O(N⁴)

Thử tất cả tổ hợp 4 phần tử.

Giải pháp 2: Theo dõi 4 max và 4 min (O(N))

• Giữ mx1..mx4 (4 số lớn nhất) và mn1..mn4 (4 số nhỏ nhất).
• Tích max = max(mx1*mx2*mx3*mx4, mn1*mn2*mn3*mn4, mx1*mx2*mn1*mn2).

Giải pháp 3: Sắp xếp (O(N log N))

• Sắp xếp mảng.
• So sánh 3 tổ hợp: 4 số lớn nhất, 4 số nhỏ nhất, 2 lớn nhất × 2 nhỏ nhất.

Ví dụ minh họa (Cách 3 - Sắp xếp)

#include <bits/stdc++.h>
using namespace std;

int findMaxProdQuad(int arr[], int n) {
    sort(arr, arr + n);
    int maxVal = max(arr[n-1]*arr[n-2]*arr[n-3]*arr[n-4], arr[0]*arr[1]*arr[2]*arr[3]);
    maxVal = max(maxVal, arr[n-1]*arr[n-2]*arr[0]*arr[1]);
    return maxVal;
}

int main() {
    int arr[] = {4, -2, 5, -6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum product of quadruple is " << findMaxProdQuad(arr, n);
    return 0;
}

Đầu ra

Maximum product of quadruple is 480