इस समस्या में, हमें n पूर्णांकों का एक सरणी arr[] दिया जाता है। हमारा काम सरणी के पहले तत्व से शुरू होने वाले अधिकतम योग वैकल्पिक अनुक्रम को खोजने के लिए एक प्रोग्राम बनाना है।
एक प्रत्यावर्ती क्रम वह क्रम है जिसमें तत्व एक क्रम में बढ़ रहे हैं और घट रहे हैं यानी पहले घट रहे हैं, फिर बढ़ रहे हैं, फिर घट रहे हैं। यहाँ, अधिकतम योग ज्ञात करने के लिए विपरीत प्रत्यावर्ती क्रम मान्य नहीं है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {5, 1, 6, 2, 4, 8, 9} आउटपुट
27
स्पष्टीकरण
Starting element: 5, decrease: 1, increase: 6, decrease: 2, increase:4, N.A. Here, we can use 4, 8, 9 as the last element of the subsequence. Sum = 5 + 1 + 6 + 2 + 4 + 9 = 27
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हम एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। इसके लिए, हम एआर [i] के साथ समाप्त होने वाले तत्वों के अधिकतम योग को संग्रहीत करने के लिए दो सरणियों का उपयोग करेंगे, जहां गिरफ्तारी [i] बढ़ रही है। अन्य एआर [i] के साथ समाप्त होने वाले तत्वों की अधिकतम राशि को स्टोर करने के लिए, जहां एआर [i] घट रहा है।
फिर हम जाँच करके तत्वों को एक जोड़ देंगे कि क्या वे बाद में बारी-बारी से कर रहे हैं। प्रत्येक सरणी के लिए, हम इंडेक्स तक अधिकतम योग की गणना करेंगे। और n तत्वों को पार करने के बाद अधिकतम मान लौटाएं।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include<iostream>
#include<cstring>
using namespace std;
int maxVal(int x, int y){
if(x > y)
return x;
return y;
}
int calcMaxSumAltSubSeq(int arr[], int n) {
int maxSum = −10000;
int maxSumDec[n];
bool isInc = false;
memset(maxSumDec, 0, sizeof(maxSumDec));
int maxSumInc[n];
memset(maxSumInc, 0, sizeof(maxSumInc));
maxSumDec[0] = maxSumInc[0] = arr[0];
for (int i=1; i<n; i++) {
for (int j=0; j<i; j++) {
if (arr[j] > arr[i]) {
maxSumDec[i] = maxVal(maxSumDec[i],
maxSumInc[j]+arr[i]);
isInc = true;
}
else if (arr[j] < arr[i] && isInc)
maxSumInc[i] = maxVal(maxSumInc[i],
maxSumDec[j]+arr[i]);
}
}
for (int i = 0 ; i < n; i++)
maxSum = maxVal(maxSum, maxVal(maxSumInc[i],
maxSumDec[i]));
return maxSum;
}
int main() {
int arr[]= {8, 2, 3, 5, 7, 9, 10};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum sum alternating subsequence starting is "<<calcMaxSumAltSubSeq(arr , n);
return 0;
} आउटपुट
The maximum sum alternating subsequence starting is 25