এই সমস্যায়, আমাদেরকে পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়েছে (ধনাত্মক পাশাপাশি নেতিবাচক)। আমাদের কাজ হল C++ এ সর্বাধিক পণ্যসুবারে গণনা করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা সমাধান − এখানে, আমাদের একটি অ্যারে রয়েছে যাতে ধনাত্মক, ঋণাত্মক এবং শূন্য সংখ্যা রয়েছে। আমাদের অ্যারের উপাদান দ্বারা তৈরি সাবয়ারের গুণফল খুঁজে বের করতে হবে। এবং সাবয়ারের পণ্য সর্বাধিক করুন।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {-1, 2, -7, -5, 12, 6} আউটপুট
5040
ব্যাখ্যা
সর্বাধিক পণ্য সহ সাবয়ারে হল {2, -7, -5, 12, 6}
৷Product = 5040
সমাধান পদ্ধতি
এই সমস্যাটি সমাধান করার জন্য, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে এবং সাবয়ারের সর্বাধিক পণ্য এবং ম্যাক্সভ্যাল পরিচালনা করি যা বর্তমান উপাদান পর্যন্ত সর্বাধিক পণ্য এবং মিনভ্যাল হল পণ্যের নেতিবাচক সর্বোচ্চ। তারপর বর্তমান মানের উপর ভিত্তি করে, maxVal এবং minVal −
হিসাবে আপডেট করা হয়কেস 1 - উপাদান ইতিবাচক − অ্যারে গুন করে maxVal এবং minVal আপডেট করুন।
কেস 2 - উপাদান শূন্য − বর্তমান সাব্যারে ভেঙ্গে 0 দিয়ে গুণ করলে 0 হবে।
কেস 3 - উপাদান নেতিবাচক − উভয় মানকেই নেতিবাচক মান দিয়ে আপডেট করুন যাতে এটির সর্বোচ্চ পরিমাণ হয়৷
৷আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
int min(int a, int b){
if(a < b)
return a;
return b;
}
int max(int a, int b){
if(a > b)
return a;
return b;
}
int CalcMaxProductSubArray(int arr[], int n) {
int i = 0;
int maxVal = -1000;
int localMax = 1;
int localMin = 1;
int lastMax;
while(i < n) {
int currentVal = arr[i];
if (currentVal > 0) {
localMax = (localMax * currentVal);
localMin = min(1, localMin * currentVal);
}
else if (currentVal < 0) {
lastMax = localMax;
localMax = (localMin * currentVal);
localMin = (lastMax * currentVal);
} else {
localMin = 1;
localMax = 0;
}
maxVal = max(maxVal, localMax);
if (localMax <= 0)
localMax = 1;
i++;
}
return maxVal;
}
int main(){
int arr[] = { -1, 2, -7, -5, 12, 6 };
int n = 6;
cout<<"The maximum product Subarray is "<<CalcMaxProductSubArray(arr, n);
return 0;
} আউটপুট
The maximum product Subarray is 5040
