C++ প্রোগ্রামে সাইজ 3 এর ক্রমবর্ধমান অনুক্রমের সর্বাধিক পণ্য

এই সমস্যায়, আমাদেরকে n ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল সাইজ 3 এর ক্রমবর্ধমান অনুক্রমের সর্বাধিক পণ্য খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।

সমস্যা বর্ণনা − এখানে, আমাদের অ্যারের 3টি উপাদানের সর্বাধিক গুণফল খুঁজে বের করতে হবে যাতে তারা একটি ক্রমবর্ধমান অনুসূচী গঠন করে এবং অ্যারে সূচকও বৃদ্ধি পায় অর্থাৎ

arr[i]*arr[j]*arr[k] সর্বাধিক, arr[i] 

 সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক, 
 
ইনপুট
 
arr ={5, 9, 2, 11, 4, 7}
 
আউটপুট
 
495
 
ব্যাখ্যা
 <প্রে>অবস্থাকে সন্তুষ্ট করে 3 আকারের সমস্ত সাবয়ারে হল (5, 9, 11), prod =5*9*11 =495(2, 4, 7), prod =2*4*7 =56 সর্বোচ্চ =495

সমাধান পদ্ধতি

সমস্যা সমাধানের একটি সহজ পদ্ধতি হল অ্যারে লুপ করা এবং প্রদত্ত শর্ত পূরণকারী 3-এর সমস্ত সাব্যারে খুঁজে পাওয়া।

উপাদানগুলির পণ্য খুঁজুন এবং সমস্ত পণ্যের সর্বাধিক ফেরত দিন৷

অ্যালগরিদম

শুরু করুন −

maxProd =−1000

ধাপ 1 −

লুপ i −> 0 থেকে n−3

পদক্ষেপ 1.1৷ −

লুপ j −> i থেকে n−2

ধাপ 1.1.1৷ −

if(arr[i] লুপ k −> j থেকে n−1

ধাপ 1.1.1.1৷ −

if(arr[j]  prod =arr[i]*arr[j]*arr[k] খুঁজুন।

ধাপ 1.1.1.2৷ −

if(maxProd> prod) −> maxProd =prod।

ধাপ 2 −

 maxProd ফেরত দিন।

উদাহরণ

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,

#include নেমস্পেস ব্যবহার করে std;int calcMaxProd(int arr[], int n){ int maxProd =−1000; int prod; (int i =0; i  
আউটপুট
 
আকার 3-এর ক্রমবর্ধমান অনুক্রমের সর্বাধিক গুণফল হল 495
 

 এই সমাধানটি সহজ কিন্তু 3টি নেস্টেড লুপ ব্যবহার করে যা O(n3) অর্ডারের সময় জটিলতা তৈরি করে। সুতরাং, আসুন সমস্যার একটি কার্যকর সমাধান দেখি,
 

 এই সমাধানে, আমরা সূচক 1 থেকে n−2 পর্যন্ত অ্যারের উপাদানগুলি নেব। এবং এটিকে আমাদের 3টি উপাদান সাবয়ারের মধ্যম উপাদান হিসাবে বিবেচনা করুন। এবং তারপর অ্যারে থেকে বাকি দুটি উপাদান খুঁজুন।
 
অ্যারের চেয়ে ছোট এলিমেন্ট i এর চেয়ে কম সূচক সহ অ্যারেতে। aar[i] এর চেয়ে বড় এলিমেন্ট i এর চেয়ে বেশি সূচক সহ অ্যারেতে।
 

 ক্ষুদ্রতম উপাদানটি একটি স্ব-ভারসাম্যপূর্ণ বাইনারি অনুসন্ধান ট্রি ব্যবহার করে পাওয়া যায় এবং সবচেয়ে বড়টির জন্য, আমরা ডান থেকে বামে অতিক্রম করব এবং ডানদিকে সর্বাধিক উপাদানটি খুঁজে পাব৷
 

 উভয় মান খুঁজে বের করার পর, আমরা উপাদান সাবয়ারের প্রোড খুঁজে পাব এবং তারপর সবকটি তুলনা করে maxProd খুঁজে বের করব।
 
উদাহরণ
 

 আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম, 
 
#includeনেমস্পেস ব্যবহার করে std;long calMaxSubSeqProd(int arr[] , int n) { int smallerLeftEle[n]; smallerLeftEle[0] =−1; সেটছোট; জন্য (int i =0; i =1; i−−) { if (arr[i]> greaterRightEle) greaterRightEle =arr[i]; অন্যথায় যদি (smallerLeftEle[i] !=−1){ prod =smallerLeftEle[i]*arr[i]*greaterRightEle; if(prod> maxProd) maxProd =prod; } } রিটার্ন maxProd;}int main() { int arr[] ={5, 9, 2, 11, 4, 7}; int n =sizeof(arr)/sizeof(arr[0]); cout<<"আকার 3-এর ক্রমবর্ধমান অনুক্রমের সর্বাধিক গুণফল হল "< 
আউটপুট
 
আকার 3-এর ক্রমবর্ধমান অনুক্রমের সর্বাধিক গুণফল হল 495