इस समस्या में, हमें एक ऐरे दिया गया है। हमारा कार्य एक ऐसा प्रोग्राम बनाना है जो ऐरे में अधिकतम ट्रिपलेट सम ढूंढे यानी तीन एलिमेंट्स का समूह ढूंढे जिसका योग अधिकतम हो।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट − array = {4, 6, 1, 2}
आउटपुट − 12
व्याख्या −
सभी ट्रिपलेट्स हैं : (4, 6, 1) = 4+6+1 = 11 (4, 6, 2) = 4+6+1 = 12 (4, 1, 2) = 4+6+1 = 7 (6, 1, 2) = 4+6+1 = 9 अधिकतम ट्रिपलेट सम 12 है
समस्या को हल करने का एक सरल दृष्टिकोण वह है जिसे हमने उदाहरण में दर्शाया है, जो सभी ट्रिपलेट जोड़ियों के योग मान ले रहा है और फिर उनमें से अधिकतम ढूंढ रहा है। लेकिन यह दृष्टिकोण प्रभावी नहीं है क्योंकि ऐरे की लंबाई के साथ सभी ट्रिपलेट्स की संख्या बड़ी हो जाएगी।
इस विधि में, हम तीन लूप चलाएंगे जो सभी संभावित योग ट्रिपलेट्स ढूंढेंगे और यदि इस ट्रिपलेट का योग मैक्ससम से बड़ा है तो हम इस ट्रिपलेट योग को मैक्ससम के रूप में प्रारंभ करेंगे।
उदाहरण
हमारे समाधान को स्पष्ट करने वाला प्रोग्राम,
#include <iostream> using namespace std; int maxSum(int arr[], int n){ int maxSum = 0; int i, j, k; for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) for (k = j + 1; k < n; k++) if (maxSum < arr[i] + arr[j] + arr[k]) maxSum = arr[i] + arr[j] + arr[k]; return maxSum; } int main(){ int arr[] = { 3, 5, 7 ,1, 9, 0 }; int n = sizeof(arr) / sizeof(arr[0]); cout<<"The maximum triplet sum of the array is "<<maxSum(arr, n); return 0; }आउटपुट
The maximum triplet sum of the array is 21
एक प्रभावी दृष्टिकोण ऐरे को सॉर्ट करना और फिर ऐरे के अंतिम तीन एलिमेंट्स का योग ढूंढना होगा जो ट्रिपलेट्स का अधिकतम योग होगा।
उदाहरण
समाधान को स्पष्ट करने वाला प्रोग्राम,
#include <bits/stdc++.h> using namespace std; int maxSum(int arr[], int n) { sort(arr, arr + n); return arr[n - 1] + arr[n - 2] + arr[n - 3]; } int main() { int arr[] = { 3, 5, 9, 1, 2, 8, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout<<"The maximum triplet sum of the array is "<<maxSum(arr, n); return 0; }आउटपुट
The maximum triplet sum of the array is 24
