C++ এ i

ধারণা

n আকারের ধনাত্মক পূর্ণসংখ্যার একটি প্রদত্ত অ্যারের সাপেক্ষে, ট্রিপলেটের সর্বাধিক যোগফল নির্ধারণ করা আমাদের কাজ ( a_i + a_j + a_k ) যেমন 0 <=i i j k .

ইনপুট

a[] = 3 6 4 2 5 10

আউটপুট

19

ব্যাখ্যা

All possible triplets are:-
3 4 5 => sum = 12
3 6 10 => sum = 19
3 4 10 => sum = 17
4 5 10 => sum = 19
2 5 10 => sum = 17
Maximum sum = 19

পদ্ধতি

এখন, একটি সরল পদ্ধতি তিনটি নেস্টেড 'ফর লুপ' সহ প্রতিটি ট্রিপলেটের জন্য পরিদর্শন করতে হবে এবং একে একে সমস্ত ট্রিপলেটের যোগফল আপডেট করতে হবে। এখানে, এই পদ্ধতির সময় জটিলতা হল O(n^3) যা 'n'-এর উচ্চ মানের জন্য যথেষ্ট নয়।

আবার, আমরা একটি উন্নত পদ্ধতি প্রয়োগ করতে পারি উপরের পদ্ধতিতে আরও অপ্টিমাইজেশন করার জন্য। এই পদ্ধতিতে, তিনটি নেস্টেড লুপ সহ প্রতিটি ট্রিপলেট ভিজিট করার পরিবর্তে, আমরা দুটি নেস্টেড লুপের মাধ্যমে পরিদর্শন করতে পারি।

প্রতিটি সংখ্যার মাধ্যমে পরিদর্শন করার সময়(মাঝারি উপাদান হিসেবে ধরা যাক(a_j )), সর্বোচ্চ সংখ্যা নির্ধারণ করুন(a_i ) a_j থেকে কম এর আগে এবং সর্বাধিক সংখ্যা(ak) a_j এর চেয়ে বড় এর বাইরে. অবশেষে, এখন, a_i এর গণনাকৃত যোগফল সহ সর্বাধিক উত্তর আপডেট করুন + a_j + a_k

উদাহরণ

// C++ program to find maximum triplet sum
#include <bits/stdc++.h>
using namespace std;
// Shows function to calculate maximum triplet sum
int maxTripletSum(int arr1[], int n1){
   // Used to initialize the answer
   int ans1 = 0;
   for (int i = 1; i < n1 - 1; ++i) {
      int max1 = 0, max2 = 0;
      // Determine maximum value(less than arr1[i])
      // from i+1 to n1-1
      for (int j = 0; j < i; ++j)
         if (arr1[j] < arr1[i])
            max1 = max(max1, arr1[j]);
      // Determine maximum value(greater than arr1[i])
      // from i+1 to n1-1
      for (int j = i + 1; j < n1; ++j)
         if (arr1[j] > arr1[i])
            max2 = max(max2, arr1[j]);
      // store maximum answer
      if(max1 && max2)
         ans1=max(ans1,max1+arr1[i]+max2);
   }
   return ans1;
}
// Driver code
int main(){
   int Arr[] = { 3, 6, 4, 2, 5, 10 };
   int N = sizeof(Arr) / sizeof(Arr[0]);
   cout << maxTripletSum(Arr, N);
   return 0;
}

আউটপুট

19