C++ में एक सरणी में ट्रिपलेट्स का अधिकतम योग खोजें जैसे कि i < j < k और a[i] < a[j] < a[k]

अवधारणा

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

इनपुट

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

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

प्रत्येक संख्या (मान लें मध्य तत्व a_j) पर जाते समय, उसके पहले अधिकतम संख्या (a_i) निर्धारित करें जो a_j से कम हो और उसके बाद अधिकतम संख्या (a_k) निर्धारित करें जो a_j से बड़ी हो। अंत में, गणना किए गए योग a_i + a_j + a_k के साथ अधिकतम उत्तर को अपडेट करें।

उदाहरण

// C++ program to find maximum triplet sum #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] से कम)       // i+1 से n1-1 तक       for (int j = 0; j < i; ++j)          if (arr1[j] < arr1[i])             max1 = max(max1, arr1[j]);       // अधिकतम मान निर्धारित करें (arr1[i] से बड़ा)       // i+1 से n1-1 तक       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