इस समस्या में, हमें N पूर्णांकों की एक सरणी arr[] और दो अनुक्रमणिका मान x और y दिए गए हैं। हमारा काम एक प्रोग्राम बनाना है जो उपसर्ग से अधिकतम योग वृद्धि को खोजने के लिए और उपसर्ग के बाद दिए गए तत्व को C++ में होना चाहिए।
समस्या का विवरण
हम अनुक्रमणिका x तक बढ़ते अनुक्रम का अधिकतम योग और अनुक्रमणिका y पर तत्व सहित पाएंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6 आउटपुट
26
स्पष्टीकरण
हम अनुक्रमणिका 3 तक अनुवर्ती कार्रवाई करेंगे और फिर अंत में गिरफ्तारी [6] =11 शामिल करेंगे।
अनुवर्ती {1, 5, 9, 11} है। योग =1+5+9+11 =26
समाधान दृष्टिकोण
एक सरल तरीका यह है कि x अनुक्रमणिका तक एक नई सरणी बनाई जाए और फिर अंत में अनुक्रमणिका y पर तत्व जोड़ा जाए। फिर सभी बढ़ते क्रमों की गणना करें और फिर उन सभी को छोड़ दें जिनमें arr[y] तत्व शामिल नहीं हो सकता है, और अधिकतम राशि ज्ञात करें।
समस्या को हल करने के लिए एक और प्रभावी तरीका एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग कर रहा है। विचार 2-डी सरणी डीपी [] [] बनाना है, और बाद में बढ़ते हुए अधिकतम योग को संग्रहीत करना है। DP[x][y] पर मान, तत्व arr[y] सहित अनुक्रमणिका x तक अधिकतम योग देगा।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#include <iostream>
using namespace std;
int DP[100][100];
void preCalcMaxSum(int arr[], int N){
for (int i = 0; i < N; i++) {
if (arr[i] > arr[0])
DP[0][i] = arr[i] + arr[0];
else
DP[0][i] = arr[i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[j] > arr[i] && j > i) {
if (DP[i - 1][i] + arr[j] > DP[i - 1][j])
DP[i][j] = DP[i - 1][i] + arr[j];
else
DP[i][j] = DP[i - 1][j];
}
else
DP[i][j] = DP[i - 1][j];
}
}
}
int main() {
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
preCalcMaxSum(arr, N);
cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
cout<<DP[x][y];
return 0;
} आउटपुट
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26
एक कुशल दृष्टिकोण अनुक्रमणिका x तक बढ़ते क्रम का अधिकतम योग इस प्रकार ज्ञात करने के लिए प्रयोग कर रहा है कि अनुक्रम का सबसे बड़ा अवयव अनुक्रमणिका y पर अवयव से कम हो। इसके लिए हम फिर से गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#include <iostream>
using namespace std;
int calcMaxSum(int arr[], int n, int x, int y){
int DP[x] = {0};
int maxSum = -1;
for (int i = 0; i <= x; i++)
DP[i] = arr[i];
for (int i = 0; i <= x; i++) {
if (arr[i] >= arr[y]) {
continue;
}
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j])
DP[i] += arr[j];
maxSum = max(maxSum, DP[i]);
}
}
if (maxSum == -1) {
return arr[y];
}
return maxSum + arr[y];
}
int main(){
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
cout<<calcMaxSum(arr, N, x, y);
return 0;
} आउटपुट
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26