C++ प्रोग्राम में विशिष्ट अंतर वाले युग्मों का अधिकतम योग

इस समस्या में, हमें n पूर्णांकों की एक सरणी arr[] और एक संख्या d दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में विशिष्ट अंतर वाले युग्मों का अधिकतम योग ढूंढे।

समस्या विवरण

हम ऐसे युग्म ढूंढेंगे जिनके तत्वों का अंतर d से कम हो। ऐसे सभी युग्मों का योग अधिकतम होना चाहिए।

उदाहरण

इनपुट

arr[] = {5, 9, 11, 7, 2, 12, 3} d = 5

आउटपुट

47

व्याख्या

अधिकतम योग में योगदान देने वाले युग्म: (3, 5), (7, 9), (11, 12)। योग = 3 + 5 + 7 + 9 + 11 + 12 = 47

समाधान दृष्टिकोण

समस्या का एक सरल और स्पष्ट समाधान सरणी के सभी मान्य युग्म बनाना और फिर योग ढूंढकर सभी योगों में से अधिकतम वापस करना है। लेकिन यह समाधान कुशल नहीं है।

समस्या का एक कुशल समाधान डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करना है। यहां, हम इष्टतम युग्म ढूंढेंगे जो अधिकतम योग बनाते हैं। इसके लिए हम क्रमबद्ध सरणी का उपयोग करेंगे, इसलिए पहले हम दी गई सरणी को क्रमबद्ध करेंगे और फिर उस पर काम करेंगे। योग ढूंढने के लिए, हम एक सरणी का उपयोग करेंगे जो वर्तमान तत्व तक युग्मों के अधिकतम योग को संग्रहीत करेगी। इसके लिए, हम जांचेंगे कि क्या वर्तमान तत्व और पिछला तत्व एक युग्म बनाते हैं। यदि हां, तो हम युग्म योग को सरणी के maxSum में जोड़ देंगे। अन्यथा, max sum वही रहेगा।

एल्गोरिदम

आरंभीकरण: DP[n]

चरण 1 -

सरणी arr[] के लिए।

चरण 2

DP[0] = 0;

चरण 3 -

लूप i → 1 से n तक

चरण 3.1 -

जांचें कि क्या पिछले तत्व के साथ युग्म संभव है। if(arr[i] - arr[i-1] < d)।

चरण 3.2 -

यदि हां, तो जांचें कि क्या वर्तमान युग्म योग अंतिम विचारित योग से अधिक मान देता है और अधिकतम मान को वर्तमान योग में जोड़ें। यानी if( (DP[i-2] + arr[i-1] + arr[i]) > (DP[i-1])) → DP[i] = (DP[i-2] + arr[i-1] + arr[i]), else → DP[i] = DP[i-1]।

चरण 3.3 -

i = 1 के मान के लिए एक अपवाद है, जहां DP[i-2] का कोई मान संभव नहीं है, इस मामले में, DP[i-2] पर विचार नहीं किया जाता क्योंकि यह पहला युग्म योग है।

चरण 4 -

DP[n-1] वापस करें।

उदाहरण

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

#include <bits/stdc++.h> 
using namespace std; 

int CalcmaxPairSum(int arr[], int n, int d) { 
    sort(arr, arr+n); 
    int maxSumDP[n]; 
    maxSumDP[0] = 0; 
    
    for (int i = 1; i < n; i++) { 
        maxSumDP[i] = maxSumDP[i-1]; 
        if (arr[i] - arr[i-1] < d) { 
            if (i >= 2) 
                if(maxSumDP[i] < (maxSumDP[i-2] + arr[i-1] + arr[i])) 
                    maxSumDP[i] = (maxSumDP[i-2] + arr[i-1] + arr[i]); 
            else 
                if(maxSumDP[i] < (arr[i-1] + arr[i])) 
                    maxSumDP[i] = arr[i-1] + arr[i]; 
        } 
    } 
    return maxSumDP[n-1]; 
} 

int main() { 
    int arr[] = {5, 9, 11, 7, 2, 12, 3}; 
    int n = 7, d = 5; 
    cout<<"The maximum sum of pairs with specific difference is "<<CalcmaxPairSum(arr, n, d); 
    return 0; 
}

आउटपुट

The maximum sum of pairs with specific difference is 47