Hiểu bài toán

Bài toán yêu cầu tìm hai phần tử trong mảng số nguyên sao cho tích của chúng là lớn nhất. Hai phần tử này phải ở các vị trí khác nhau trong mảng. Input là số lượng phần tử n và mảng A gồm n số nguyên. Constraints: 2 ≤ n ≤ 10^4, |A_i| ≤ 10^4. Output là giá trị tích lớn nhất tìm được.

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

Cách Brute Force (Lặp kép)

#include <stdio.h>

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

    long long max_product = -1e18; // Khởi tạo giá trị âm rất nhỏ
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            long long product = a[i] * a[j];
            if(product > max_product) {
                max_product = product;
            }
        }
    }
    printf("%lld", max_product);
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Phương pháp này sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các cặp phần tử có thể có trong mảng. Với mỗi cặp (i, j) mà i < j, nó tính tích và so sánh với giá trị tích lớn nhất tìm được cho đến thời điểm đó. Đây là cách tiếp cận trực quan nhất nhưng không hiệu quả về mặt thời gian với n lên tới 10^4 (khoảng 100 triệu phép tính).

Cách Sắp xếp và Tìm kiếm

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

int cmp(const void *a, const void *b) {
    long long x = *(const long long*)a;
    long long y = *(const long long*)b;
    if (x > y) return 1;
    if (x < y) return -1;
    return 0;
}

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

    // Sắp xếp mảng tăng dần
    qsort(a, n, sizeof(long long), cmp);

    // Tích lớn nhất có thể là tích của 2 số lớn nhất (cuối mảng)
    // hoặc tích của 2 số nhỏ nhất (đầu mảng) nếu chúng âm
    long long product1 = a[n-1] * a[n-2];
    long long product2 = a[0] * a[1];

    if(product1 > product2) {
        printf("%lld", product1);
    } else {
        printf("%lld", product2);
    }

    return 0;
}

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

Sau khi sắp xếp mảng tăng dần, tích lớn nhất chỉ có thể nằm ở một trong hai vị trí: (1) Tích của hai số lớn nhất (a[n-1] và a[n-2]), hoặc (2) Tích của hai số nhỏ nhất (a[0] và a[1]). Lý do là vì nếu có số âm, tích của hai số âm lớn nhất (nghĩa là xa 0 nhất) có thể lớn hơn tích của hai số dương nhỏ nhất. Ví dụ: [-10, -9, 1, 2], tích lớn nhất là (-10)*(-9)=90. Phương pháp này hiệu quả hơn nhiều so với Brute Force.

Cách Tối ưu O(n) - Duyệt một lần

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

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

    // Tìm 2 giá trị lớn nhất và 2 giá trị nhỏ nhất
    long long max1 = LLONG_MIN, max2 = LLONG_MIN;
    long long min1 = LLONG_MAX, min2 = LLONG_MAX;

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

        if(a[i] < min1) {
            min2 = min1;
            min1 = a[i];
        } else if(a[i] < min2) {
            min2 = a[i];
        }
    }

    long long product1 = max1 * max2;
    long long product2 = min1 * min2;

    if(product1 > product2) {
        printf("%lld", product1);
    } else {
        printf("%lld", product2);
    }

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n) (hoặc O(1) nếu lưu trực tiếp vào biến)

Thay vì sắp xếp toàn bộ mảng, ta chỉ cần duyệt qua mảng một lần để tìm ra 2 số lớn nhất và 2 số nhỏ nhất. Tích lớn nhất sẽ là tích của một trong hai cặp này. Cách này tối ưu nhất về thời gian thực thi vì chỉ cần duyệt qua mảng đúng một lần.

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

Bài học kinh nghiệm

• Vấn đề chỉ quan tâm đến giá trị, không quan tâm đến vị trí gốc của các phần tử trong mảng đầu vào (miễn là chúng khác nhau).
• Tích lớn nhất chỉ có thể xảy ra ở 2 trường hợp: tích của hai số lớn nhất hoặc tích của hai số nhỏ nhất (nếu có số âm).
• Sử dụng long long là bắt buộc để tránh tràn số整数 (integer overflow), vì tích của hai số có thể lên tới 10^8, nằm trong giới hạn của int (2*10^9), nhưng để an toàn và tránh lỗi logic với số âm lớn, long long là lựa chọn chuẩn.

Lỗi thường gặp

• Quên kiểm tra trường hợp số âm: Nếu chỉ lấy hai số lớn nhất, có thể bỏ lỡ tích lớn nhất từ hai số âm (ví dụ: -100 và -99 cho tích 9900, lớn hơn 1*2=2).
• Tràn số (Integer Overflow): Dùng int để tính tích có thể gây tràn số nếu hai số đều dương hoặc đều âm lớn (gần 10^4).
• Lỗi truy cập mảng: Trong solution 2 và 3 của người dùng, họ dùng mảng bắt đầu từ chỉ số 1, nhưng khai báo a[n] (từ 0 đến n-1) hoặc a[n+3]. Solution 2 in ra %d cho biến max là long long (sai kiểu format), Solution 3 dùng bubble sort không tối ưu.