Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम में डायनामिक प्रोग्रामिंग का उपयोग करके अधिकतम योग बढ़ता उपअनुक्रम


इस समस्या में, हमें आकार n की एक सरणी arr[] दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में डायनामिक प्रोग्रामिंग का उपयोग करके अधिकतम योग बढ़ता उपअनुक्रम ढूंढे।

समस्या विवरण

अधिकतम योग बढ़ते उपअनुक्रम को ढूंढने के लिए, हम एक उपअनुक्रम बनाएंगे जिसमें अगला तत्व वर्तमान तत्व से अधिक हो।

उदाहरण

इनपुट

arr[] = {4, 2, 3, 6, 5, 9}

आउटपुट

20

व्याख्या

अधिकतम योग वाला बढ़ता उपअनुक्रम: {2, 3, 6, 9} = 2 + 3 + 6 + 9 = 20

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

समस्या को डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करके हल करने के लिए। हम वर्तमान तत्व तक के अधिकतम योग को संग्रहीत करने के लिए एक सरणी बनाएंगे। फिर सरणी से maxSum वापस करेंगे।

उदाहरण

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

#include <iostream> 
using namespace std; 

int retMaxVal(int x, int y){ 
    if(x > y) 
        return x; 
    return y; 
} 

int calcMaxSubSeqSum(int arr[], int n) { 
    int maxSum = 0; 
    int sumDP[n]; 
    for (int i = 0; i < n; i++ ) 
        sumDP[i] = arr[i]; 
    
    for (int i = 1; i < n; i++ ) 
        for (int j = 0; j < i; j++ ) 
            if ( (sumDP[i] < (sumDP[j] + arr[i])) && ( arr[i] > arr[j] ) ) 
                sumDP[i] = sumDP[j] + arr[i]; 
    
    for (int i = 0; i < n; i++ ) 
        maxSum = retMaxVal(sumDP[i], maxSum); 
    
    return maxSum; 
} 

int main() { 
    int arr[] = {4, 2, 3, 6, 5, 9}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout<<"The maximum Sum Increasing Subsequence using DP is "<<calcMaxSubSeqSum(arr, n); 
    return 0; 
}

आउटपुट

Sum of maximum sum increasing subsequence is 20
  1. - C++ का उपयोग करके मैट्रिक्स में अधिकतम योग वाला कॉलम खोजें

    मान लीजिए हमारे पास M x N आकार का एक मैट्रिक्स है। हमें वह कॉलम ढूंढना है जिसका योग अधिकतम है। इस प्रोग्राम में हम किसी ट्रिकी दृष्टिकोण का पालन नहीं करेंगे, बल्कि सरणी को कॉलम-वार पार करेंगे, प्रत्येक कॉलम का योग प्राप्त करेंगे, और यदि योग अधिकतम है, तो उस योग और कॉलम इंडेक्स को प्रिंट करेंगे। उदा

  1. - C++ में डिवाइड एंड कंकर का उपयोग करके अधिकतम योग सबएरे

    मान लीजिए हमारे पास धनात्मक और ऋणात्मक मानों के साथ डेटा की एक सूची है। हमें सन्निहित सबएरे का योग ढूंढना है जिसका योग सबसे बड़ा है। मान लीजिए सूची में {-2, -5, 6, -2, -3, 1, 5, -6} है, तो अधिकतम सबएरे का योग 7 है। यह {6, -2, -3, 1, 5} का योग है।हम इस समस्या को डिवाइड एंड कंकर विधि का उपयोग करके हल

  1. - C++ में बाइनरी सर्च दृष्टिकोण का उपयोग करके अधिकतम सबएरे योग ज्ञात करना

    बाइनरी सर्च एक तेज खोज एल्गोरिदम है जिसकी रन-टाइम जटिलता O(log n) है। यह एल्गोरिदम विभाजन और विजय के सिद्धांत पर काम करता है। इस एल्गोरिदम के ठीक से काम करने के लिए, डेटा संग्रह सॉर्टेड रूप में होना चाहिए। बाइनरी सर्च संग्रह के मध्य तत्व की तुलना करके किसी विशेष आइटम को खोजता है। यदि मेल होता है, त