কনসেপ্ট
একটি ধনাত্মক পূর্ণসংখ্যার অ্যারে দেওয়া আছে যার আকার n। আমাদের কাজ হল ট্রিপলেট (aᵢ + aⱼ + aₖ) এর সর্বোচ্চ যোগফল নির্ণয় করা যেন 0 ≤ i < j < k < n এবং aᵢ < aⱼ < aₖ।
ইনপুট
a[] = 3 6 4 2 5 10
আউটপুট
19
ব্যাখ্যা
সম্ভাব্য সব ট্রিপলেট: 3 4 5 => যোগফল = 12 3 6 10 => যোগফল = 19 3 4 10 => যোগফল = 17 4 5 10 => যোগফল = 19 2 5 10 => যোগফল = 17 সর্বোচ্চ যোগফল = 19
পদ্ধতি
সহজ পদ্ধতি: তিনটি নেস্টেড 'for লুপ' ব্যবহার করে প্রতিটি ট্রিপলেট যাচাই করুন এবং যোগফল আপডেট করুন। এই পদ্ধতির টাইম কমপ্লেক্সিটি O(n³) যা বড় n-এর জন্য উপযুক্ত নয়।
উন্নত পদ্ধতি: তিনটি নেস্টেড লুপের পরিবর্তে দুটি নেস্টেড লুপ ব্যবহার করুন। প্রতিটি উপাদান (মাঝপথের উপাদান aⱼ হিসেবে বিবেচনা করে) এর জন্য, তার আগের চেয়ে ছোট সর্বোচ্চ উপাদান (aᵢ) এবং পেছনের চেয়ে বড় সর্বোচ্চ উপাদান (aₖ) খুঁজে বের করুন। তারপর aᵢ + aⱼ + aₖ যোগফল দিয়ে সর্বোচ্চ উত্তর আপডেট করুন।
উদাহরণ (C++ কোড)
// C++ প্রোগ্রাম: ট্রিপলেটের সর্বোচ্চ যোগফল খুঁজে বের করার জন্য
#include <bits/stdc++.h>
using namespace std;
// ট্রিপলেটের সর্বোচ্চ যোগফল গণনা করার ফাংশন
int maxTripletSum(int arr1[], int n1) {
int ans1 = 0; // উত্তর ইনিশিয়ালাইজ
for (int i = 1; i < n1 - 1; ++i) {
int max1 = 0, max2 = 0;
// arr1[i]-এর চেয়ে ছোট সর্বোচ্চ মান বামপাশ থেকে খুঁজুন
for (int j = 0; j < i; ++j)
if (arr1[j] < arr1[i])
max1 = max(max1, arr1[j]);
// arr1[i]-এর চেয়ে বড় সর্বোচ্চ মান ডানপাশ থেকে খুঁজুন
for (int j = i + 1; j < n1; ++j)
if (arr1[j] > arr1[i])
max2 = max(max2, arr1[j]);
// যদি উভয় পাওয়া যায় তবে সর্বোচ্চ যোগফল আপডেট করুন
if (max1 && max2)
ans1 = max(ans1, max1 + arr1[i] + max2);
}
return ans1;
}
// ড্রাইভার কোড
int main() {
int Arr[] = { 3, 6, 4, 2, 5, 10 };
int N = sizeof(Arr) / sizeof(Arr[0]);
cout << maxTripletSum(Arr, N);
return 0;
}
আউটপুট
19
