এই সমস্যায়, আমাদেরকে N পূর্ণসংখ্যার একটি অ্যারে [] এবং দুটি সূচক মান 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-ডি অ্যারে ডিপি [][] তৈরি করা, এবং সর্বাধিক ক্রমবর্ধমান অনুক্রমের সমষ্টি সংরক্ষণ করা। 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
