এই সমস্যায়, আমাদেরকে পূর্ণসংখ্যার একটি অ্যারে [] এবং একটি সংখ্যা k দেওয়া হয়েছে। আমাদের কাজ হল C++-এ k-এর পরবর্তী সাইজের সর্বোচ্চ পণ্য খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা − এখানে, আমাদের k, 1<=k <=n যেটির উপাদানগুলির সর্বাধিক গুণফল আছে তার অনুক্রমটি খুঁজে বের করতে হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {1, 5, 6, -2, 0, 4} , k = 3 আউটপুট
120
ব্যাখ্যা
সাইজ 3 এর পরবর্তীতে যার সর্বোচ্চ গুণফল আছে (5, 6, 4)। পণ্যটি 120।
সমাধান পদ্ধতি
এই সমস্যাটি সমাধান করার জন্য, আমরা প্রথমে array arr[] এবং তারপর arr[] এর উপাদান এবং k এর মানের উপর ভিত্তি করে সাজাব। নিম্নলিখিত ক্ষেত্রে পদ্ধতিটি পরিবর্তিত হয় -
কেস 1 (যদি k জোড় হয়) − পণ্যটিতে 0 ব্যতীত সমস্ত সর্বাধিক k মান থাকতে পারে। এখানে, আমাদের ঋণাত্মক মান জোড়া বিবেচনা করতে হবে। যেহেতু তাদের মাত্রাও সর্বোচ্চ ফলাফল দিতে পারে।
কেস 2 (যদি k বিজোড় হয়) − এটি কিছুটা জটিল অবস্থা এবং মানগুলি নির্ধারণ করে যে ফলাফলটি কীভাবে গণনা করা দরকার। এই কেসটিকে অ্যারের সর্বোচ্চ উপাদানের উপর ভিত্তি করে আরও শ্রেণীবদ্ধ করা দরকার।
কেস 2.1 (যদি সর্বোচ্চ সংখ্যা ইতিবাচক হয়) - এর মানে হল অ্যারেটি ধনাত্মক এবং ঋণাত্মক সংখ্যার মিশ্রণ। এই ক্ষেত্রে, আমরা সর্বাধিক k উপাদানগুলি খুঁজে পাব এবং নেতিবাচক দিক থেকে সর্বাধিক জোড়াগুলিও অনুসন্ধান করব (যদি সম্ভব হয় তবে এটি ফলাফল দিতে পারে)।
কেস 2.2 (যদি সর্বোচ্চ সংখ্যা শূন্য হয়) − এর মানে অ্যারেতে সমস্ত নেতিবাচক উপাদান এবং শূন্য রয়েছে। এই ক্ষেত্রে, সর্বাধিক ফলাফল হবে 0, কারণ নেতিবাচক উপাদানগুলির একটি বিজোড় সংখ্যাকে গুণ করলে একটি ঋণাত্মক সংখ্যা হবে, যার অর্থ হল 0 হল সর্বাধিক গুণ।
কেস 2.3 (যদি সর্বোচ্চ সংখ্যা নেতিবাচক হয়) - এর মানে অ্যারেতে শুধুমাত্র ঋণাত্মক সংখ্যা রয়েছে। এই ক্ষেত্রে, ন্যূনতম মাত্রা সহ উপাদানগুলিকে গুণ করে সর্বাধিক ফলাফল প্রদান করা হবে অর্থাৎ সর্বাধিক অ্যারে সাহায্য করবে৷
এইভাবে, সর্বোত্তম ফলাফলের জন্য আমাদের উপাদানগুলির পাশাপাশি k এর মান পরীক্ষা করতে হবে। এর জন্য, ফলাফলের সাথে ঋণাত্মক জোড়াকে গুণ করে ফলাফল পাওয়া যায় কিনা তা পরীক্ষা করার জন্য আমরা সর্বোচ্চ এবং নূন্যতম উভয় দিকেই রাখব।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int findMaxSubArrayProduct(int arr[], int n, int k) {
sort(arr, arr + n);
int maxProd = 1;
int i = 0, j = 0;
int maxprod, minprod;
if (arr[n - 1] == 0 && (k % 2 == 1))
return 0;
if (arr[n - 1] <= 0 && (k % 2 == 1)) {
for (i = n - 1; i >= n - k; i--)
maxProd *= arr[i];
return maxProd;
}
i = 0;
j = n - 1;
if (k % 2 == 1) {
maxProd *= arr[j];
j--;
k--;
}
k = k/2;
int it = 0;
while(it < k){
int minprod = arr[i] * arr[i + 1];
int maxprod = arr[j] * arr[j - 1];
if (minprod > maxprod) {
maxProd *= minprod;
i += 2;
} else {
maxProd *= maxprod;
j -= 2;
}
it++;
}
return maxProd;
}
int main() {
int arr[] = { 1, 5, 6, -2, 0, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"The maximum product of subsequence of size "<<k<<" is "<<findMaxSubArrayProduct(arr, n, k);
return 0;
} আউটপুট
The maximum product of subsequence of size 3 is 120
