Hiểu bài toán

Cho một mảng gồm n số nguyên. Tìm ba phần tử tại ba vị trí khác nhau trong mảng sao cho tích của chúng là lớn nhất. Với n ≤ 10^4 và giá trị phần tử ≤ 1000, ta cần tìm cách giải quyết hiệu quả để tránh TLE (Time Limit Exceeded) và OLE (Output Limit Exceeded).

Các cách tiếp cận

Cách Brute Force

for (int i = 0; i < n; i++) {
  for (int j = i + 1; j < n; j++) {
    for (int k = j + 1; k < n; k++) {
      // Tính tích và so sánh
    }
  }
}

• Time Complexity: O(n^3)
• Space Complexity: O(1)

Duyệt qua tất cả các bộ 3 phần tử có thể có trong mảng. Với n lên tới 10^4, số lượng bộ 3 là khoảng 10^12, quá lớn để chạy trong thời gian cho phép.

Cách Sắp xếp mảng (Sorting)

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int n; scanf("%d", &n);
    int a[n];
    for(int i=0; i<n; i++) scanf("%d", &a[i]);
    qsort(a, n, sizeof(int), cmp);

    long long max1 = 1LL * a[0] * a[1] * a[n-1];
    long long max2 = 1LL * a[n-1] * a[n-2] * a[n-3];

    if (max1 > max2) printf("%lld", max1);
    else printf("%lld", max2);
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(1)

Sắp xếp mảng tăng dần. Tích lớn nhất có thể là tích của 3 số lớn nhất nhất (cuối mảng) hoặc tích của 2 số nhỏ nhất (âm lớn nhất) và 1 số lớn nhất (dương). Ta chỉ cần so sánh hai trường hợp này. Ví dụ: [-100, -100, 1, 2, 3] -> max(123, (-100)(-100)3).

Cách Duyệt một lần (Linear Scan)

#include <stdio.h>
#include <limits.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
    int min1 = INT_MAX, min2 = INT_MAX;

    for (int i = 0; i < n; i++) {
        int x = a[i];
        // Update max
        if (x > max1) { max3 = max2; max2 = max1; max1 = x; }
        else if (x > max2) { max3 = max2; max2 = x; }
        else if (x > max3) { max3 = x; }

        // Update min
        if (x < min1) { min2 = min1; min1 = x; }
        else if (x < min2) { min2 = x; }
    }

    long long p1 = 1LL * max1 * max2 * max3;
    long long p2 = 1LL * min1 * min2 * max1;

    if (p1 > p2) printf("%lld", p1);
    else printf("%lld", p2);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Thay vì sắp xếp, ta chỉ cần duyệt qua mảng một lần để tìm 3 số lớn nhất và 2 số nhỏ nhất. Logic tương tự cách sắp xếp nhưng tối ưu hơn về mặt thời gian chạy (thường nhanh hơn do chỉ truy cập dữ liệu một lượt).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán chỉ quan tâm đến giá trị lớn nhất của tích, không cần quan tâm đến thứ tự xuất hiện của các số trong mảng ban đầu.
• Tích lớn nhất chỉ có thể được tạo ra từ các 'ứng cử viên' край điểm của mảng đã sắp xếp (hoặc các giá trị max/min khi duyệt linear).

Lỗi thường gặp

• Tràn số (Integer Overflow): Tích của 3 số (100010001000 = 10^9) có thể vượt quá giới hạn của kiểu int (2*10^9). Phải dùng kiểu dữ liệu lớn hơn như long long.
• Quên xử lý trường hợp số âm: Hai số âm nhân với nhau ra số dương, nếu nhân tiếp với một số dương lớn thì tích có thể lớn hơn tích của 3 số dương.