इस समस्या में, हमें N पूर्णांकों की एक सरणी arr[] दी गई है। हमारा कार्य C++ में अधिकतम योग घटता हुआ सबसीक्वेंस ढूंढना है।
समस्या विवरण
हम सरणी से तत्वों का अधिकतम योग ढूंढेंगे जैसे कि सबसीक्वेंस सख्ती से घटता हुआ हो।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
arr[] = {3, 1, 6, 10, 5, 2, 9}
आउटपुट
17
व्याख्या
अधिकतम योग वाला घटता हुआ सबसीक्वेंस {10, 5, 2} = 10 + 5 + 2 = 17 है।
समाधान दृष्टिकोण
यहां, हम समाधान खोजने के लिए डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। यहां, हम एक maxSum[] सरणी बनाएंगे जो इंडेक्स 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