এই সমস্যায়, আমাদেরকে n পূর্ণসংখ্যার সমন্বয়ে একটি অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল অ্যারেতে ট্রিপলেটের সর্বোচ্চ গুণফল (আকার 3 এর পরবর্তী) খুঁজে বের করা। এখানে, আমরা সর্বাধিক পণ্যের মান সহ ট্রিপল খুঁজে বের করব এবং তারপর পণ্যটি ফেরত দেব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {9, 5, 2, 11, 7, 4} আউটপুট
693
ব্যাখ্যা
এখানে, আমরা ট্রিপলেটটি খুঁজে পাব যা অ্যারের সমস্ত উপাদানের সর্বোচ্চ গুণফল দেয়। maxProd =9 * 11 * 7 =693
সমাধান পদ্ধতি
সমস্যার একাধিক সমাধান হতে পারে। আমরা এখানে সেগুলি নিয়ে আলোচনা করব,
৷পদ্ধতি 1
সরাসরি পদ্ধতি এই পদ্ধতিতে, আমরা সরাসরি অ্যারের মাধ্যমে লুপ করব এবং তারপর সম্ভাব্য সমস্ত ট্রিপলেট খুঁজে বের করব। প্রতিটি ট্রিপলেটের উপাদানগুলির গুণফল খুঁজে বের করুন এবং তাদের সবকটির সর্বাধিক প্রদান করুন৷
৷অ্যালগরিদম
শুরু করুন
maxProd = −1000
ধাপ 1 :
Create three nested loops: Loop 1:i −> 0 to n−3 Loop 2: j −> i to n−2 Loop 3: k −> j to n−1
পদক্ষেপ 1.1৷ −
Find the product, prod = arr[i]*arr[j]*arr[k].
পদক্ষেপ 1.2৷ −
if prod > maxProd −> maxProd = prod.
ধাপ 3 −
return maxProd.
উদাহরণ
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
int maxProd = −1000;
int prod;
for (int i = 0; i < n − 2; i++)
for (int j = i + 1; j < n − 1; j++)
for (int k = j + 1; k < n; k++){
prod = arr[i] * arr[j] * arr[k];
if(maxProd < prod)
maxProd = prod;
}
return maxProd;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is "<<calcMaxProd(arr, n);
return 0;
} আউটপুট
Maximum product of a triplet in array is 693
পদ্ধতি 2
বাছাই ব্যবহার করে
এই পদ্ধতিতে, আমরা অ্যারেকে অবরোহী ক্রমে সাজাব। সাজানো অ্যারেতে, সর্বাধিক পণ্য ট্রিপলেট হবে,
(arr[0], arr[1], arr[2]) (arr[0], arr[1], arr[2])
আমরা এই ট্রিপলেটের সর্বোচ্চ গুণফল ফেরত দেব।
অ্যালগরিদম
ধাপ 1 −
Sort the given array in descending order.
ধাপ 2 −
Find product of triples, maxTriplet1 = arr[0]*arr[1]*arr[2] maxTriplet2 = arr[0]*arr[n−1]*arr[n−2]
ধাপ 3 −
if( maxTriplet1 > maxTriplet2 ) −> return maxTriplet1
পদক্ষেপ 4৷ −
else −> return maxTriplet2.
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <bits/stdc++.h>
using namespace std;
int calcMaxProd(int arr[], int n){
sort(arr, arr + n, greater<>());
int maxTriplet1 = arr[0]*arr[1]*arr[2];
int maxTriplet2 = arr[0]*arr[n−1]*arr[n−2];
if(maxTriplet1 > maxTriplet2)
return maxTriplet1;
return maxTriplet2;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is
"<<calcMaxProd(arr, n);
return 0;
} আউটপুট
অ্যারেতে ট্রিপলেটের সর্বোচ্চ গুণফল হল 693
পদ্ধতি 3
ট্রিপলেট মান খোঁজা।
আমরা এখন জানি যে সর্বাধিক পণ্য ট্রিপলেট হতে পারে দুটি ট্রিপলেটের যেকোনো একটি থেকে,
(maximum, second_max, third_max) (maximum, minimum, second_min)
সুতরাং, আমরা অ্যারে অতিক্রম করে সরাসরি এই মানগুলি খুঁজে পেতে পারি, এবং তারপর মানগুলি ব্যবহার করে, আমরা সর্বাধিক পণ্য ট্রিপলেট খুঁজে পাব৷
অ্যালগরিদম
শুরু করুন
max =-1000, secMax =-1000, thirdMax =-1000 , min =10000, secMin =10000
ধাপ 1 −
loop the array i −> 0 to n−1.
পদক্ষেপ 1.1৷
if(arr[i] > max) −> thirdMax = secMax, secMax = max, max = arr[i]
পদক্ষেপ 1.2৷ −
elseif(arr[i] > secMax) −> thirdMax = secMax, secMax = arr[i]
পদক্ষেপ 1.3৷ −
elseif(arr[i] > thirdMax) −> thirdMax = arr[i]
পদক্ষেপ 1.4৷ −
if(arr[i] < min) −> secMin = min, min = arr[i]
পদক্ষেপ 1.4৷ −
elseif(arr[i] < secMin) −> secMin = arr[i]
ধাপ 2 −
triplet1 = max * secMax * thridMax triplet2 = max * min * secMin
ধাপ 3 −
if(triplet1 > triplet2) −> return triplet1
পদক্ষেপ 4৷ −
else −> return triplet2
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
int max = −1000, secMax = −1000, thirdMax = −1000;
int min = 1000, secMin = 1000;
for (int i = 0; i < n; i++){
if (arr[i] > max){
thirdMax = secMax;
secMax = max;
max = arr[i];
}
else if (arr[i] > secMax){
thirdMax = secMax;
secMax = arr[i];
}
else if (arr[i] > thirdMax)
thirdMax = arr[i];
if (arr[i] < min){
secMin = min;
min = arr[i];
}
else if(arr[i] < secMin)
secMin = arr[i];
}
int triplet1 = max * secMax * thirdMax;
int triplet2 = max * secMin * min;
if(triplet1 > triplet2)
return triplet1;
return triplet2;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is
"<<calcMaxProd(arr, n);
return 0;
} আউটপুট
Maximum product of a triplet in array is 693
