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

समस्या विवरण

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

इसके लिए हमें N पूर्णांकों वाली एक सरणी प्रदान की जाएगी। हमारा कार्य सरणी से तत्वों को चुनना है जो अधिकतम योग में जुड़ते हैं जैसे कि तत्व क्रमबद्ध क्रम में हों।

C++ कार्यान्वयन

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

int maxSumIS(int arr[], int n) {
    int i, j, max = 0;
    int msis[n];
    for ( i = 0; i < n; i++ )
        msis[i] = arr[i];
    for ( i = 1; i < n; i++ )
        for ( j = 0; j < i; j++ )
            if (arr[i] > arr[j] &&
                msis[i] < msis[j] + arr[i])
                msis[i] = msis[j] + arr[i];
    for ( i = 0; i < n; i++ )
        if ( max < msis[i] )
            max = msis[i];
    return max;
}

int main() {
    int arr[] = {1, 101, 2, 3, 100, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Sum of maximum sum increasing subsequence is "<<
        maxSumIS( arr, n ) << endl;
    return 0;
}

आउटपुट

Sum of maximum sum increasing subsequence is 106