C++ में i <j <k और a[i] <a[j] <a[k] की तुलना में किसी सरणी में त्रिक का अधिकतम योग ज्ञात करें

अवधारणा

आकार n के धनात्मक पूर्णांकों के दिए गए सरणी के संबंध में, ट्रिपलेट का अधिकतम योग निर्धारित करने का हमारा कार्य ( a_i + ए<उप>जे + ए<उप>के ) जैसे कि 0 <=i i जे के ।

इनपुट

a[] = 3 6 4 2 5 10

आउटपुट

स्पष्टीकरण

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' के उच्च मान के लिए पर्याप्त नहीं है।

फिर से, हम एक बेहतर दृष्टिकोण apply लागू कर सकते हैं उपरोक्त दृष्टिकोण में और अनुकूलन करने के लिए। इस पद्धति में, तीन नेस्टेड लूप वाले प्रत्येक ट्रिपल के माध्यम से जाने के बजाय, हम दो नेस्टेड लूप के माध्यम से जा सकते हैं।

प्रत्येक संख्या के माध्यम से जाने के समय (मध्य तत्व के रूप में जाने दें (a_j .) )), अधिकतम संख्या निर्धारित करें (a_i ) a_j . से कम इससे पहले और अधिकतम संख्या (ak ) a_j . से बड़ी है इस से परे। अंत में, अब, अधिकतम उत्तर को _i . के परिकलित योग के साथ अपडेट करें + ए<उप>जे + ए<उप>के

उदाहरण

// 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;
}