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

सर्कुलर ऐरे में अधिकतम योग जहाँ कोई दो आसन्न तत्व न हों - C++


इस समस्या में, हमें एक सर्कुलर ऐरे cirArr[] दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में सर्कुलर ऐरे में अधिकतम योग ढूंढे जहाँ कोई दो आसन्न तत्व न हों।

समस्या विवरण

सर्कुलर ऐरे के लिए, हमें ऐरे के तत्वों का अधिकतम योग ढूंढना है जहाँ आसन्न तत्वों को नहीं लिया जा सकता, यानी हमें वैकल्पिक तत्व लेने हैं।

सर्कुलर ऐरे एक विशेष प्रकार का ऐरे है जिसमें ऐरे का अंतिम तत्व पहले तत्व से जुड़ा होता है।

सर्कुलर ऐरे में अधिकतम योग जहाँ कोई दो आसन्न तत्व न हों - C++

आइए एक उदाहरण से इस समस्या को समझते हैं,

इनपुट

cirArr[] = {4, 1, 5, 3, 2}

आउटपुट

9

व्याख्या

अधिकतम योग वाला सर्कुलर सबसीक्वेंस है [4, 5, 2]। योग = 9

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

इस समस्या का समाधान डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करके अधिकतम योग ढूंढना है। योग को सर्कुलर ऐरे को दो ऐरे के रूप में मानकर निकाला जा सकता है, एक इंडेक्स 0 से N-2 तक और दूसरा इंडेक्स 1 से n-1 तक। इससे दो ऐरे बनेंगे और इन ऐरे के योगों में से अधिकतम योग परिणाम होगा।

उदाहरण

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

#include <iostream> using namespace std; int calcMaxVal(int a, int b){    if(a > b)       return a;    return b; } int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {    int DP[n];    int maxSum = 0;    for (int i = start; i < (end + 1); i++) {       DP[i] = cirArr[i];       if (maxSum < cirArr[i])          maxSum = cirArr[i];    }    for (int i = (start + 2); i < (end + 1); i++) {       for (int j = 0; j < i - 1; j++) {          if (DP[i] < DP[j] + cirArr[i]) {             DP[i] = DP[j] + cirArr[i];             if (maxSum < DP[i])                maxSum = DP[i];          }       }    }    return maxSum; } int findMaxSum(int cirArr[], int n){    int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, (n-2), n);    int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, (n-1), n);    int maxSum = calcMaxVal(maxSumArray1, maxSumArray2);    return maxSum; } int main(){    int cirArr[] = {4, 1, 5, 3, 2};    int n = sizeof(cirArr)/sizeof(cirArr[0]);    cout<<"The maximum sum in circular array such that no two elements are adjacent is "<<findMaxSum(cirArr, n);    return 0; }

आउटपुट

The maximum sum in circular array such that no two elements are adjacent is 9

  1. - C++ प्रोग्राम में ऐरे में दूरी < K पर कोई दो तत्व न आने पर सब-सीक्वेंस के लिए अधिकतम संभव योग

    समस्या विवरण इस समस्या में, हमें आकार n का एक ऐरे arr[] और एक पूर्णांक k दिया गया है। हमारा कार्य ऐसा प्रोग्राम बनाना है जो ऐरे में दूरी < K पर कोई दो तत्व न आने पर सब-सीक्वेंस के लिए अधिकतम संभव योग ढूंढे। समस्या विवरण - हमें सब-सीक्वेंस का अधिकतम योग ढूंढना है जो उन तत्वों पर विचार करता है जो एक द

  1. - C++ प्रोग्राम में दो सरणियों के उत्पादों का अधिकतम योग

    इस समस्या में, हमें आकार n की दो सरणियाँ arr1[] और arr2[] दी गई हैं। हमारा कार्य एक प्रोग्राम बनाना है जो दो सरणियों के उत्पादों का अधिकतम योग ढूंढे। समस्या विवरण हमें दो सरणियों के उत्पादों का अधिकतम योग ढूंढना है। हमें arr1 के एक तत्व और arr2 के अन्य तत्वों के उत्पाद का अधिकतम योग ढूंढना है। उद

  1. C++ प्रोग्राम में डायनामिक प्रोग्रामिंग का उपयोग करके बाइनरी ट्री में आसन्न न होने वाले नोड्स का अधिकतम योग C++ प्रोग्राम में डायनामिक प्रोग्रामिंग का उपयोग करके बाइनरी ट्री में आसन्न न होने वाले नोड्स का अधिकतम योग

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें प्रत्येक नोड का एक मान है। हमारा कार्य एक प्रोग्राम बनाना है जो डायनामिक प्रोग्रामिंग का उपयोग करके बाइनरी ट्री में ऐसे नोड्स का अधिकतम योग ढूंढे जो आसन्न न हों। समस्या विवरण हम बाइनरी ट्री के उपसमुच्चय (subsets) को चुनेंगे ताकि योग अधिकतम हो औ