Tích lớn nhất của bộ ba (dãy con độ dài 3) trong mảng C++

Cho mảng số nguyên. Tìm bộ ba 3 phần tử (không cần liên tiếp, không cần tăng) có tích lớn nhất.

Thuật toán

• Với N nhỏ: thử tất cả O(N³).
• Với N lớn: sắp xếp, so sánh tích 3 số lớn nhất vs 2 số nhỏ nhất (âm) × số lớn nhất.
• Code mẫu dùng O(N³) cho đơn giản.

Ví dụ triển khai (C++)

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

int maxProduct(int arr[], int n) {
    if (n < 3) return -1;
    int max_product = INT_MIN;
    for (int i = 0; i < n-2; i++)
        for (int j = i+1; j < n-1; j++)
            for (int k = j+1; k < n; k++)
                max_product = max(max_product, arr[i] * arr[j] * arr[k]);
    return max_product;
}

int main() {
    int arr[] = {10, 3, 5, 6, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max = maxProduct(arr, n);
    if (max == -1) cout << "No Triplet Exists";
    else cout << "Maximum product is " << max;
    return 0;
}

Đầu ra

Maximum product is 1200