इस समस्या में, हमें n आकार का एक सरणी arr[] दिया जाता है। हमारा कार्य C++ में DP का उपयोग करते हुए अधिकतम योग वृद्धि को खोजने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण - अधिकतम योग वृद्धि के बाद का पता लगाने के लिए, हम एक ऐसा क्रम बनाएंगे जिसमें अगला तत्व वर्तमान तत्व से बड़ा होगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {4, 2, 3, 6, 5, 9} आउटपुट
20
स्पष्टीकरण
Increasing subsequence with maximum sum:
{2, 3, 6, 9} = 2 + 3 + 6 + 9 = 20 समाधान दृष्टिकोण
एक गतिशील कार्यक्रम दृष्टिकोण का उपयोग करके समस्या को हल करने के लिए। हम वर्तमान तत्व तक अधिकतम योग को संग्रहीत करने के लिए एक सरणी बनाएंगे। फिर सरणी से themaxSum लौटाएं।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#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