समस्या विवरण
इस समस्या में, हमें N पूर्णांकों की एक सरणी arr[] और दो सूचकांक मान x और y दिए गए हैं। हमारा कार्य C++ में एक उपसर्ग से अधिकतम योग बढ़ते उपअनुक्रम को खोजने के लिए एक प्रोग्राम बनाना है और उपसर्ग के बाद एक दिया गया तत्व अनिवार्य है।
हम इंडेक्स x तक बढ़ते क्रम का अधिकतम योग ढूंढेंगे और इंडेक्स y पर तत्व को शामिल करेंगे।
उदाहरण
इनपुट
arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6
आउटपुट
26
व्याख्या
हम इंडेक्स 3 तक उपअनुक्रम लेंगे और अंत में arr[6] = 11 को शामिल करेंगे।
उपअनुक्रम है {1, 5, 9, 11}। योग = 1+5+9+11 = 26
समाधान दृष्टिकोण
एक सरल दृष्टिकोण x इंडेक्स तक एक नई सरणी बनाना और फिर अंत में इंडेक्स y पर तत्व जोड़ना है। फिर सभी बढ़ते उपअनुक्रमों की गणना करें और फिर उन सभी को छोड़ दें जो तत्व arr[y] को शामिल नहीं कर सकते, और maxSum ढूंढें।
समस्या को हल करने का एक और प्रभावी दृष्टिकोण डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करना है। विचार एक 2-D सरणी DP[][] बनाने का है, और बढ़ते उपअनुक्रम के अधिकतम योग को संग्रहीत करना है। DP[x][y] पर मान इंडेक्स x तक तत्व arr[y] को शामिल करके अधिकतम योग देगा।
C++ कार्यान्वयन (2-D DP)
#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
कुशल दृष्टिकोण (1-D DP)
इंडेक्स 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