এই সমস্যায়, আমাদেরকে পূর্ণসংখ্যার একটি অ্যারে [] দেওয়া হয়েছে। আমাদের কাজ হল সর্বাধিক প্রোডাক্ট সাবারে খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা - দুইটি ট্রাভার্সালসিন C++ ব্যবহার করে।
সমস্যা বর্ণনা − এখানে অ্যারেতে, আমরা সূচক 0 থেকে একটি এবং আরেকটি সূচক (n-1) দুটি ট্রাভার্সাল ব্যবহার করে সর্বাধিক পণ্য সাব্যারে খুঁজে পাব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, -2, 5, -6, 0, 8} আউটপুট
240
উদাহরণ
Subarray = {4, -2, 5, -6}
Maximum product = 4 * (-2) * 5 * (-6) = 240 সমাধান পদ্ধতি
দুটি ট্রাভার্সাল ব্যবহার করে এই সমস্যাটি সমাধান করতে। এখানে, আমরা বাম থেকে ডানে অর্থাৎ সূচক 0 থেকে n-1 পর্যন্ত ট্রাভার্সালের জন্য দুটি স্থানীয় সর্বোচ্চ মান ব্যবহার করে সর্বাধিক পণ্যটি খুঁজে পাব। এবং একটি ডান থেকে বামে ট্রাভার্সালের জন্য অর্থাৎ indexn-1 থেকে 0 পর্যন্ত। বাকি অ্যালগরিদমটি সর্বাধিক পণ্যসুবারে খোঁজার মতই।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include<iostream>
using namespace std;
int CalcMaxProductSubArray(int arr[], int n) {
int frntMax = 1, rearMax = 1, maxVal = 1;
for (int i=0; i<n; i++) {
frntMax = frntMax*arr[i];
if (frntMax == 0)
frntMax = 1;
}
for (int i=n-1; i>=0; i--) {
rearMax = rearMax * arr[i];
if (rearMax == 0)
rearMax = 1;
}
maxVal = max(frntMax, rearMax);
return maxVal;
}
int main() {
int arr[] = {4, -2, 5, -6, 0, 8};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Maximum product subarray is "<<CalcMaxProductSubArray(arr, n);
return 0;
} আউটপুট
Maximum product subarray is 240
