ডাইনামিক প্রোগ্রামিং ব্যবহার করে সর্বোচ্চ যোগফল বাড়মান সাবসিকোয়েন্স (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n আকারের একটি অ্যারে arr[] দেওয়া আছে। আমাদের কাজ হল ডাইনামিক প্রোগ্রামিং ব্যবহার করে সর্বোচ্চ যোগফল বাড়মান সাবসিকোয়েন্স খুঁজে বের করার C++ প্রোগ্রাম তৈরি করা।

সর্বোচ্চ যোগফল বাড়মান সাবসিকোয়েন্স খুঁজে বের করার জন্য, আমরা একটি সাবসিকোয়েন্স তৈরি করব যেখানে পরবর্তী উপাদান বর্তমান উপাদানের চেয়ে বড় হবে।

arr[] = {4, 2, 3, 6, 5, 9}

20

সর্বোচ্চ যোগফল বাড়মান সাবসিকোয়েন্স: {2, 3, 6, 9} = 2 + 3 + 6 + 9 = 20

ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করে সমস্যা সমাধান করতে হবে। আমরা বর্তমান উপাদান পর্যন্ত সর্বোচ্চ যোগফল সংরক্ষণ করার জন্য একটি অ্যারে তৈরি করব। তারপর অ্যারেতে থেকে সর্বোচ্চ যোগফল ফেরত দিব।

#include 
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