Tìm 3 số có tích lớn nhất trong mảng

[Thu_Phuong (Thu Phương)]

Với một dãy số nguyên cho trước, hãy viết hàm int maximumProduct (char * path) tìm bộ ba số có tích lớn nhất trong tất cả các bộ số và trả về tích lớn nhất đó.

Hàm nhận đầu vào là đường dẫn đến tệp lưu mảng số nguyên cho trước. Hàm trả về tích lớn nhất có thể có.

Dòng đầu tiên của tệp chứa kích cỡ n, dòng kế tiếp chứa n số nguyên cách nhau bởi một khoảng trắng.

int maximumProduct (char * path) {
    ifstream file(path);
    int n;
    file >> n;
    int a[n];
    for (int i=0; i<n; i++) {
        file >> a[i];
    }
    for (int i=0; i<n-1; i++) {
        for (int j=i+1; j<n; j++) {
            if(a[i]<a[j]) {
                int temp= a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    if (a[0]*a[1]>=a[n-1]*a[n-2]) return a[0]*a[1]*a[2];
    else return a[0]*a[n-1]*a[n-2];
}

thuật toán của em như thế này nhưng trong một vài trường hợp vẫn sai và em không biết đó là trường hợp nào vì ko thể xem được mảng số nguyên mà đề bài cho sẵn. Các anh chị có thể xem giúp em xem lỗi ở đâu không ạ. Em cảm ơn ạ

[kisuluoibieng (Tên Gì Cũng Được)]

bạn đã tính tới trường hợp số âm chưa?

[Thu_Phuong (Thu Phương)]

Mình tính rồi. Mình sắp xếp mảng giảm dần sau đó so sánh tích của 2 số lớn với tích của 2 số bé nhất , nếu tích 2 số lớn nhất lớn hơn thì trả về tích của 3 số ở đầu mảng ( 3 số lớn nhất ) còn nếu ko thì trả về tích của 2 phần tử bé nhất và phần tử lớn nhất

[Stanley00 (Stanley)]

Lấy ví dụ mảng sau thì đáp án của bạn là gì? : 200 100 0 -10 -20

[Thu_Phuong (Thu Phương)]

nếu như trong trường hợp này thì code của mình lại sai rồi, bạn có cách nào tối ưu hơn không, rất mong được chỉ giáo ạ

[rogp10]

Đầu tiên chia mảng ra số âm và số không âm (cái này ko cần mảng phụ), rồi lập bảng xét dấu.

[kisuluoibieng (Tên Gì Cũng Được)]

sai/chưa xong thì có gì đâu mà tối ưu
bạn phải phân tích lại để đưa ra 1 bài giải đúng, giờ đã có mấy cái ví dụ rồi, bạn cần xử lý thêm những case bị thiếu sót, rồi khi nào bạn xử lý xong hết, thì mới tính tới chuyện “tối ưu” chứ

[hungaya (Hung)]

Ban đầu sắp xếp mảng theo chiều giảm dần giá trị tuyệt đối của phần tử.
Tiếp theo tìm 3 phần tử đầu tiên (không nhất thiết liên tiếp) thoả mãn một trong 4 điều kiện sau:

• +++
• +--
• -+-
• --+

trong đó -+- tương ứng phần tử đầu tiên là số âm, phần tử thứ hai là số dương, và phần tử thứ ba là số âm.

Nếu không tìm được, thì xét trường hợp “chứa số 0” và “tích âm”.

[rogp10]

Có thể tìm max/min thứ k trong O(kn) mà.

Bài này có thể đưa về so sánh min*min_2 của số âm và max_2*max_3 của số không âm, sau khi loại trừ trường hợp n = 3 hay toàn số âm.

[library (La biblioteca)]

Không biết tớ có sót TH nào không, cơ mà sau khi sắp xếp mảng, tích lớn nhất hoặc là của 3 số lớn nhất, hoặc là của số lớn nhất với 2 số bé nhất thôi phải không?

[Thai_Ha (Thái Hà)]

1. Sắp xếp mảng không cần thiết: Thuật toán của bạn sắp xếp mảng theo thứ tự giảm dần, nhưng điều này không cần thiết vì chúng ta chỉ cần tìm bộ ba số có tích lớn nhất, không cần phải sắp xếp toàn bộ mảng.
2. Không xử lý trường hợp khi cả ba số âm: Thuật toán của bạn không xử lý trường hợp khi cả ba số trong mảng đều âm. Điều này có thể gây ra lỗi trong kết quả trả về.
3. Chưa kiểm tra kích cỡ mảng đúng cách: Thuật toán không xử lý trường hợp khi mảng đầu vào có ít hơn 3 phần tử.

mình code lại đây nhé

int maximumProduct (char * path) {
    ifstream file(path);
    int n;
    file >> n;
    if (n < 3) {
        // Trả về thông báo lỗi hoặc giá trị mặc định tùy thuộc vào yêu cầu của bài toán
        return -1;
    }
    int a[n];
    for (int i=0; i<n; i++) {
        file >> a[i];
    }
    // Sắp xếp mảng theo thứ tự tăng dần
    sort(a, a + n);
    
    // Trường hợp cả ba số là dương hoặc 2 số âm nhỏ nhất nhân với số dương lớn nhất
    int option1 = a[n-1] * a[n-2] * a[n-3];
    // Trường hợp cả ba số là âm
    int option2 = a[0] * a[1] * a[n-1];
    
    return max(option1, option2);
}