আমাদের N আকারের পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়েছে। এখানে লক্ষ্য হল সর্বাধিক এবং সর্বনিম্ন পণ্য উপসেটগুলি খুঁজে বের করা। আমরা দুটি পণ্য ভেরিয়েবল নিয়ে এটি করব, একটি এখন পর্যন্ত পাওয়া ন্যূনতম পণ্যের জন্য minProd এবং অন্যটি এখন পর্যন্ত পাওয়া সর্বাধিক পণ্যের জন্য, maxProd৷
অ্যারেটি অতিক্রম করার সময় আমরা প্রতিটি উপাদানকে minProd এবং maxProd উভয় দিয়ে গুণ করব। এছাড়াও পূর্ববর্তী সর্বোচ্চ পণ্য, পূর্ববর্তী সর্বনিম্ন পণ্য, বর্তমান সর্বোচ্চ পণ্য, বর্তমান সর্বনিম্ন পণ্য এবং বর্তমান উপাদান নিজেই পরীক্ষা করে দেখুন।
ইনপুট
Arr[]= { 1,2,5,0,2 } আউটপুট
Maximum Product: 20 Minimum Product: 0
ব্যাখ্যা − maxProd এবং minProd মান সহ অ্যারের দ্বিতীয় উপাদান থেকে শুরু করে 1 ( প্রথম উপাদান) দিয়ে শুরু করা হয়েছে৷
Arr[1]: 1*2=2, 1*2=2, maxProd=2, minProd=1 Arr[2]: 2*5=10, 1*5=5, maxProd=10, minProd=1 Arr[3]: 10*0=0, 1*0=0, maxProd=10, minProd=0 Arr[4]: 10*2=20, 0*2=0, maxProd=20, minProd=0
ইনপুট
Arr[]= { -1,2,-5,0,2 } আউটপুট
Maximum Product: 20 Minimum Product: -20
ব্যাখ্যা − সর্বাধিক পণ্যের জন্য, উপসেটের উপাদান রয়েছে- { -1,2,-5,2 }
ন্যূনতম পণ্যের জন্য, উপসেটের উপাদান রয়েছে- { 2,-5,2 }
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
পূর্ণসংখ্যা অ্যারে Arr[] ধনাত্মক এবং ঋণাত্মক পূর্ণসংখ্যা ধারণ করে।
-
পরিবর্তনশীল আকারে অ্যারের দৈর্ঘ্য থাকে।
-
GetProductSubset(int arr[], int n) ফাংশনটি অ্যারেটিকে ইনপুট হিসাবে নেয় এবং প্রাপ্ত উপাদানগুলির সর্বাধিক এবং সর্বনিম্ন পণ্য প্রদান করে৷
-
ভেরিয়েবল curMin, curMax বর্তমান সর্বাধিক এবং সর্বনিম্ন পণ্য পাওয়া যায় সংরক্ষণ করতে ব্যবহার করা হয়. প্রাথমিকভাবে arr[0]।
-
ভেরিয়েবল prevMin, prevMax পূর্ববর্তী সর্বোচ্চ এবং সর্বনিম্ন পণ্য পাওয়া যায় সংরক্ষণ করতে ব্যবহার করা হয়. প্রাথমিকভাবে arr[0]।
-
ভেরিয়েবল maxProd এবং minProd প্রাপ্ত চূড়ান্ত সর্বোচ্চ এবং সর্বনিম্ন পণ্য সংরক্ষণ করতে ব্যবহৃত হয়।
-
2য় উপাদান থেকে অ্যারে অতিক্রম করা শুরু করুন, শেষ সূচক পর্যন্ত arr[1]।
-
সর্বাধিক পণ্যের জন্য, বর্তমান arr[i] কে prevMax এবং prevMin দিয়ে গুণ করুন। curMax এ সর্বাধিক পণ্য সংরক্ষণ করুন। যদি এই curMax>prevMax, prevMax দিয়ে curMax আপডেট করুন।
-
curMax>maxProd
হলে curMax দিয়ে maxProd আপডেট করুন -
সর্বশেষে পরবর্তী পুনরাবৃত্তির জন্য curMax এর সাথে prevMax আপডেট করুন।
-
তুলনা পরিবর্তন করে prevMin, curMin এবং minProd-এর জন্য উপরের মতো একই পদক্ষেপগুলি করুন৷
-
লুপ শেষ হওয়ার পরে maxProd এবং minProd-এ প্রাপ্ত ফলাফলগুলি প্রিন্ট করুন।
উদাহরণ
#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n){
// Initialize all products with arr[0]
int curMax = arr[0];
int curMin = arr[0];
int prevMax = arr[0];
int prevMin= arr[0];
int maxProd = arr[0];
int minProd = arr[0];
int temp1=0,temp2=0,temp3=0;
// Process all elements after arr[0]
for (int i = 1; i < n; ++i){
/* Current maximum product is maximum of following
1) prevMax * current arr[i] (when arr[i] is +ve)
2) prevMin * current arr[i] (when arr[i] is -ve)
3) current arr[i]
4) Previous max product */
temp1=prevMax*arr[i];
temp2=prevMin*arr[i];
temp3=temp1>temp2?temp1:temp2;
curMax = temp3>arr[i]?temp3:arr[i];
curMax = curMax>prevMax?curMax:prevMax;
/* Current minimum product is minimum of following
1) prevMin * current arr[i] (when arr[i] is +ve)
2) prevMax * current arr[i] (when arr[i] is -ve)
3) current arr[i]
4) Previous min product */
temp1=prevMax*arr[i];
temp2=prevMin*arr[i];
temp3=temp1<temp2?temp1:temp2;
curMin = temp3<arr[i]?temp3:arr[i];
curMin = curMin<prevMin?curMin:prevMin;
maxProd = maxProd>curMax?maxProd:curMax;
minProd = minProd<curMin?minProd:curMin;
// copy current values to previous values
prevMax = curMax;
prevMin = curMin;
}
std::cout<<"Maximum Subset Product: "<<maxProd;
std::cout<<"\nMinimum Subset Product: "<<minProd;
}
int main(){
int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
// int arr[] = {-4, 1,1, 3, 5,7};
int size = 7;
getProductSubset(Arr,size ) ;
return 0;
} আউটপুট
Maximum Subset Product: 192 Minimum Subset Product: -64
