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

समस्या विवरण

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

समस्या विवरण - हमें सबऐरे का योग ढूंढना है जिसमें ऐरे के तत्व हों लेकिन ऐरे के कोई दो आसन्न तत्व विचार में न लिए जाएं।

उदाहरण

समस्या को समझने के लिए एक उदाहरण लेते हैं,

arr[] = {5, 2, 1, 9, 6}

आउटपुट

व्याख्या

सबऐरे योग हैं: {5, 1, 6}, योग = 5 + 1 + 6 = 12
{2, 9}, योग = 2 + 9 = 11

हल करने का दृष्टिकोण

यहां, हमारे पास समस्या का एक वैकल्पिक हल है जो डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करता है। इस दृष्टिकोण में, हम दी गई शर्त को पूरा करने वाले सबसीक्वेंस ढूंढेंगे और उसका अधिकतम प्रिंट करेंगे। हम एक ऐरे maxSumDP[n] बनाएंगे जो बने सबसीक्वेंस का अधिकतम योग संग्रहीत करता है। तत्व maxSumDP[i] इंडेक्स i से n-1 तक तत्वों को लेकर बने सबसीक्वेंस का अधिकतम योग संग्रहीत करता है। इसके लिए हम या तो ऐरे के वर्तमान तत्व arr[i] पर विचार कर सकते हैं यानी maxSumDP[i] = arr[i] + maxSumDP[i+2]। या ऐरे के वर्तमान तत्व arr[i] पर विचार नहीं कर सकते यानी maxSumDP[i] = maxSumDP[i+1]।

एल्गोरिदम

1. आरंभीकरण - maxSumDP[]
2. चरण 1 - maxSumDP[n-1] और maxSumDP[n-2] के मान आरंभ करें। maxSumDP[n-1] = arr[n-1] और maxSumDP[n-2] = max(arr[n-1], arr[n-2])।
3. चरण 2 - i -> n-2 से 0 तक लूप
   • चरण 2.1 - maxSumDP[i] का मान आरंभ करें, maxSumDP[i] = max(arr[i] + maxSumDP[i+2], maxSumDP[i+1])
4. चरण 3 - maxSumDP[0] वापस करें जो अधिकतम योग सीक्वेंस योग है।

उदाहरण

#include <iostream>
using namespace std;

int retMaxVal(int a, int b) {
    if (a > b) return a;
    return b;
}

int calcMaxSum(int arr[], int n) {
    int maxSumDP[n];
    maxSumDP[n-1] = arr[n-1];
    maxSumDP[n-2] = max(arr[n-1], arr[n-2]);
    for (int i = n - 3; i >= 0; i--) {
        maxSumDP[i] = retMaxVal(arr[i] + maxSumDP[i + 2], maxSumDP[i + 1]);
    }
    return maxSumDP[0];
}

int main() {
    int arr[] = { 5, 2, 1, 9, 6 };
    int n = sizeof(arr) / sizeof(int);
    cout << "The maximum subsequence sum in such a way that no two consecutive elements of the array is " << calcMaxSum(arr, n);
    return 0;
}

आउटपुट

The maximum subsequence sum in such a way that no two consecutive elements of the array is 14