इस समस्या में, हमें एन पूर्णांकों की एक सरणी गिरफ्तारी [] दी गई है। हमारा कार्य C++ में अधिकतम योग घटाने के बाद का पता लगाना है।
समस्या का विवरण
हम सरणी से तत्वों का अधिकतम योग इस तरह पाएंगे कि बाद का क्रम सख्ती से घट रहा है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {3, 1, 6, 10, 5, 2, 9} आउटपुट
17
स्पष्टीकरण
बाद में अधिकतम योग के साथ घटाना {10, 5, 2} =10 + 5 + 2 =17
हैसमाधान दृष्टिकोण
यहां, हम समाधान खोजने के लिए गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। यहां, हम एक मैक्ससम [] एरे बनाएंगे जो मैक्ससम को इंडेक्स i तक स्टोर करेगा। सरणी मानों को खोजने के लिए निम्न सूत्र का उपयोग किया जाता है,
maxSum[i] =arr[i] + max(maxSum[0 … (*i-1)])
अधिकतम योग सरणी के अधिकतम तत्व द्वारा दिया जाता है maxSum[]।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#include <iostream>
using namespace std;
int findMaxSumDecSubSeq(int arr[], int N){
int maximumSum = 0;
int maxSum[N];
for (int i = 0; i < N; i++)
maxSum[i] = arr[i];
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++)
if (arr[i] < arr[j] && maxSum[i] < maxSum[j] + arr[i])
maxSum[i] = maxSum[j] + arr[i];
for (int i = 0; i < N; i++)
if (maximumSum < maxSum[i])
maximumSum = maxSum[i];
return maximumSum;
}
int main(){
int arr[] = { 5, 4, 100, 3, 2, 101, 1 };
int N= sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum of decreasing subsequence is "<<findMaxSumDecSubSeq(arr, N);
return 0;
} आउटपुट
The maximum sum of decreasing subsequence is 106