Tìm tập con có tích lớn nhất của một mảng trong C++

Trong bài toán này, chúng ta được cung cấp một mảng arr[] gồm n giá trị nguyên. Nhiệm vụ là viết chương trình tìm Tập con có tích lớn nhất của một mảng.

Mô tả bài toán

Ở đây, ta cần tính tích lớn nhất có thể của một tập con các phần tử của mảng.

Tập con (Subset)

Mảng sub[] là tập con của mảng arr[] nếu tất cả phần tử của sub[] đều có mặt trong arr[].

Ví dụ minh họa

Đầu vào

arr[] = {4, 5, 2, -1, 3}

Đầu ra

40

Giải thích

Tập con sub[] = {4, 5, 2}
Tích = 4*5*2 = 40

Phương pháp giải

Cách đơn giản: tạo tất cả các tập con có thể của mảng. Tìm tích của chúng và trả về lớn nhất. Cách này dễ cài đặt nhưng cần lồng vòng lặp, độ phức tạp O(n² * n).

Cách hiệu quả: tính số lượng số âm (nofNeg) và số 0 (nof0) từ mảng, sau đó tính maxProd dựa trên các trường hợp:

Trường hợp 1 (nof0 = 0 và nofNeg chẵn) - Xét tất cả phần tử cho tích.
maxProd = arr[0] * arr[1] * ... * arr[n-1]

Trường hợp 2 (nof0 = 0 và nofNeg lẻ) - Xét tất cả phần tử trừ phần tử âm lớn nhất (gần 0 nhất).

Trường hợp 3 (nof0 != 0) - Bỏ qua tất cả số 0. Xét tương tự trường hợp 1 và 2.

Trường hợp đặc biệt - Chỉ có một phần tử khác 0 là số âm. maxProd = 0.

Thuật toán

Khởi tạo

maxProd = 1;

Bước 1

Duyệt mảng, đếm nof0, nofNeg, và tìm maxProd = maxProd * arr[i], i từ 0 đến n-1

Bước 2

Xét các trường hợp:
Trường hợp 1: if(nofNeg%2 == 0): maxProd
Trường hợp 2: if(nofNeg%2 != 0): maxProd = maxProd / (largestNeg)
Trường hợp 3: if(nof0 == (n-1) and nofNeg == 1), maxProd = 0.

Bước 3

In maxProd.

Chương trình minh họa

#include <iostream>
using namespace std;

int findMaxSubsetProd(int arr[], int n) {
    int larNeg = -1000;
    int nofNeg = 0, nof0 = 0;
    int maxProd = 1;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) {
            nof0++;
            continue;
        } else if (arr[i] < 0) {
            nofNeg++;
            if (larNeg < arr[i])
                larNeg = arr[i];
        }
        maxProd = maxProd * arr[i];
    }
    
    if (nofNeg % 2 == 0) {
        return maxProd;
    } else if (nofNeg % 2 != 0)
        return (maxProd / larNeg);
    
    if (nof0 == (n-1) && nofNeg == 1)
        return 0;
    
    return maxProd;
}

int main() {
    int arr[] = {4, -2, 5, -1, 3, -6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tích lớn nhất của tập con mảng là " << findMaxSubsetProd(arr, n);
    return 0;
}

Đầu ra

Tích lớn nhất của tập con mảng là 720