এই সমস্যায়, আমাদের n আকারের একটি অ্যারে অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল C++-এ DP ব্যবহার করে সর্বাধিক যোগফল বৃদ্ধির অনুক্রম খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা − সর্বাধিক যোগফল ক্রমবর্ধমান অনুক্রম খুঁজে পেতে, আমরা একটি অনুগামী তৈরি করব যেখানে পরবর্তী উপাদানটি বর্তমান উপাদানের থেকে বড়৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, 2, 3, 6, 5, 9} আউটপুট
20
ব্যাখ্যা
Increasing subsequence with maximum sum:
{2, 3, 6, 9} = 2 + 3 + 6 + 9 = 20 সমাধান পদ্ধতি
ডায়নামিক প্রোগ্রাম অ্যাপ্রোচ ব্যবহার করে সমস্যার সমাধান করতে। বর্তমান উপাদান পর্যন্ত সর্বাধিক যোগফল সংরক্ষণ করার জন্য আমরা অ্যানারে তৈরি করব। তারপর অ্যারে থেকে themaxSum ফেরত দিন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int retMaxVal(int x, int y){
if(x > y)
return x;
return y;
}
int calcMaxSubSeqSum(int arr[], int n) {
int maxSum = 0;
int sumDP[n];
for (int i = 0; i < n; i++ )
sumDP[i] = arr[i];
for (int i = 1; i < n; i++ )
for (int j = 0; j < i; j++ )
if ( (sumDP[i] < (sumDP[j] + arr[i])) && ( arr[i] >
arr[j] ) )
sumDP[i] = sumDP[j] + arr[i];
for (int i = 0; i < n; i++ )
maxSum = retMaxVal(sumDP[i], maxSum);
return maxSum;
}
int main() {
int arr[] = {4, 2, 3, 6, 5, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum Sum Increasing Subsequence using DP is
"<<calcMaxSubSeqSum(arr, n);
return 0;
} আউটপুট
Sum of maximum sum increasing subsequence is 20
