এই সমস্যায়, আমাদের N পূর্ণসংখ্যার একটি অ্যারে arr[] এবং দুটি ইন্ডেক্স মান x এবং y দেওয়া আছে। আমাদের কাজ হল সি++-এ প্রিফিক্স থেকে এবং প্রিফিক্সের পরে একটি নির্দিষ্ট উপাদান বাধ্যতামূলক থাকা সর্বোচ্চ যোগফল ওর্ডার্ড সাবসিকোয়েন্স বের করার একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
আমরা ইন্ডেক্স x পর্যন্ত ওর্ডার্ড সিকোয়েন্সের সর্বোচ্চ যোগফল বের করব এবং ইন্ডেক্স y-এ থাকা উপাদানটি অন্তর্ভুক্ত করব।
উদাহরণ দিয়ে বুঝতে চেষ্টা করি,
ইনপুট
arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6
আউটপুট
26
ব্যাখ্যা
আমরা ইন্ডেক্স ৩ পর্যন্ত সাবসিকোয়েন্স নিব এবং শেষে 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] উপাদান সহ সর্বোচ্চ যোগফল দেবে।
উদাহরণ
আমাদের সমাধানের কার্যকারিতা বোঝার জন্য প্রোগ্রাম,
#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
