সমস্যাতে, আমাদেরকে n পূর্ণসংখ্যার মানের একটি অ্যারে অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল একটি অ্যারের সর্বাধিক পণ্য উপসেট খুঁজে পেতে একটি প্রোগ্রাম তৈরি করা৷
৷সমস্যা বর্ণনা − এখানে, আমাদের একটি অ্যারের উপাদানগুলির একটি উপসেটের সর্বাধিক সম্ভাব্য গুণফল গণনা করতে হবে৷
সাবসেট − একটি অ্যারে সাব[] অ্যারে অ্যারের একটি উপসেট [] যদি সাব[] এর সমস্ত উপাদান arr[] এ উপস্থিত থাকে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, 5, 2, −1, 3} আউটপুট
40
ব্যাখ্যা
Subset sub[] = {4, 5, 2}
Prod = 4*5*2 = 40 সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য একটি সহজ এবং সহজ পদ্ধতি হল অ্যারের সমস্ত সম্ভাব্য উপসেট তৈরি করা। তাদের পণ্যগুলি খুঁজুন এবং তাদের সর্বাধিক ফেরত দিন৷
৷এই সমাধানটি বাস্তবায়ন করা সহজ কিন্তু O(n 2 ) এর ক্রমকে জটিল করে তুলতে নেস্টেড লুপগুলির প্রয়োজন *n)।
এখানে বাস্তবায়নের চেষ্টা করুন।
কার্যকর সমাধান অ্যারে থেকে নেগেটিভ’স(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
