बाद में अधिकतम योग वृद्धि | सी++ में डीपी-14

इस ट्यूटोरियल में, हम अधिकतम योग वृद्धि क्रम खोजने के लिए एक कार्यक्रम पर चर्चा करेंगे।

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
//returning the maximum sum
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