ในปัญหา เราได้รับอาร์เรย์ arr[] ของค่าจำนวนเต็ม n ค่า งานของเราคือสร้างโปรแกรมเพื่อค้นหาชุดย่อยผลิตภัณฑ์สูงสุดของอาร์เรย์
คำอธิบายปัญหา − ในที่นี้ เราต้องคำนวณผลคูณสูงสุดที่เป็นไปได้ของชุดย่อยขององค์ประกอบของอาร์เรย์
เซตย่อย − Array sub[] คือชุดย่อยของ array arr[] หากองค์ประกอบทั้งหมดของ sub[] มีอยู่ใน arr[]
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {4, 5, 2, −1, 3} ผลลัพธ์
40
คำอธิบาย
Subset sub[] = {4, 5, 2}
Prod = 4*5*2 = 40 แนวทางการแก้ปัญหา
แนวทางที่ง่ายและสะดวกในการแก้ปัญหาคือการสร้างชุดย่อยที่เป็นไปได้ทั้งหมดของอาร์เรย์ ค้นหาผลิตภัณฑ์และคืนสินค้าสูงสุด
โซลูชันนี้ใช้งานง่าย แต่ต้องใช้การวนซ้ำซ้อนทำให้ความซับซ้อนของลำดับของ O(n 2 *น)
ลองใช้ที่นี่
วิธีแก้ปัญหาที่มีประสิทธิภาพ คือโดยการคำนวณจำนวนค่าลบ (nofNeg) และค่าศูนย์ (nof0) จากอาร์เรย์แล้วคำนวณ maxProd ตามเงื่อนไขเหล่านี้
กรณีที่ 1 (nof0 =0 และ nofNeg เป็นเลขคู่)− พิจารณาองค์ประกอบทั้งหมดของอาร์เรย์ไปยังผลิตภัณฑ์
maxProd =arr[0] * arr[1] * … arr[n−1]
กรณีที่ 2 (nof0 =0 และ nofNeg เป็นเลขคี่)− พิจารณาองค์ประกอบทั้งหมดของอาร์เรย์ ยกเว้นองค์ประกอบเชิงลบที่ใหญ่ที่สุดของอาร์เรย์ (ใกล้สุดถึง 0)
กรณีที่ 3 (nof0 !=0)− ปล่อยให้ศูนย์ทั้งหมดของอาร์เรย์สำหรับผลิตภัณฑ์ และเอาเคสที่คล้ายกับกรณีที่ 1 และ 2
กรณีพิเศษ - มีเพียงองค์ประกอบเดียวยกเว้น 0 ที่เป็นค่าลบ maxProd =0.
อัลกอริทึม
เริ่มต้น −
maxProd = 1;
ขั้นตอนที่ 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
ขั้นตอนที่ 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.
ขั้นตอนที่ 3
Print maxProd.
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The maximum product subset of an array is 720
