Tập hợp con sản phẩm tối đa của một mảng trong chương trình C ++

Trong bài toán, chúng ta được cung cấp một mảng arr [] gồm n giá trị nguyên. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tập hợp con Sản phẩm tối đa của một mảng.

Mô tả sự cố - Ở đây, chúng 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ột mảng.

Tập hợp con - Một mảng con [] là một tập con của mảng arr [] nếu tất cả các phần tử của mảng con [] đều có trong arr [].

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

40

Giải thích

Subset sub[] = {4, 5, 2}
Prod = 4*5*2 = 40

Phương pháp tiếp cận giải pháp

Một cách tiếp cận đơn giản và dễ dàng để giải quyết vấn đề là tạo tất cả các tập dữ liệu có sẵn của mảng. Tìm sản phẩm của họ và trả lại tối đa.

Giải pháp này dễ thực hiện nhưng yêu cầu các vòng lặp lồng nhau tạo nên tính đơn giản của thứ tự O (n ² * n).

Hãy thử triển khai tại đây.

Giải pháp hiệu quả là bằng cách tính toán số lượng âm (nofNeg) và số không (nof0) từ mảng và sau đó tính toán maxProd dựa trên các điều kiện này.

Trường hợp 1 (nof0 =0 và nofNeg là chẵn) - Xem xét tất cả các phần tử của mảng thành tích.

maxProd =arr [0] * arr [1] *… arr [n − 1]

Trường hợp 2 (nof0 =0 và nofNeg là số lẻ) - Xem xét tất cả các phần tử của mảng ngoại trừ phần tử âm lớn nhất của mảng (gần 0 nhất).

Trường hợp 3 (nof0! =0) - Để lại tất cả các số không của mảng cho sản phẩm. Và lấy các trường hợp tương tự như trường hợp 1 và 2.

Trường hợp đặc biệt - chỉ có một phần tử trừ 0 là âm. maxProd =0.

Thuật toán

Khởi tạo -

maxProd = 1;

Bước 1 -

Loop the array and count, nof0(number of zeros) and
nofNeg(number of negatives), and find maxProd.
maxProd = maxProd*arr[i], i −> 0 to n−1

Bước 2 -

consider the following cases −
Case 1− if(nofNeg%2 == 0): maxProd
Case 2− if(nofNeg%2 != 0): maxProd = maxProd/(largestNeg)
Case 3 − if(nof0 == (n-1) and nofNeg == 1), maxProd = 0.

Bước 3

Print maxProd.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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) and nofNeg == 1)
      return 0;
   return maxProd;
}
int main(){
   int arr[] = {4, −2, 5, −1, 3, −6};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum product subset of an array is "<<findMaxSubsetProd(arr, n);
   return 0;
}

Đầu ra

The maximum product subset of an array is 720