C++-এ সর্বোচ্চ যোগফল নিম্নমুখী সাবসিকোয়েন্স (Maximum Sum Decreasing Subsequence)

এই সমস্যায় N পূর্ণসংখ্যার একটি অ্যারে arr[] দেওয়া আছে। আমাদের কাজ হল C++-এ সর্বোচ্চ যোগফল নিম্নমুখী সাবসিকোয়েন্স বের করা।

সমস্যার বিবরণ

আমরা অ্যারে থেকে এমন উপাদান বের করব যাতে সাবসিকোয়েন্সটি কঠোরভাবে নিম্নমুখী (strictly decreasing) হয় এবং তাদের যোগফল সর্বোচ্চ হয়।

উদাহরণ:

ইনপুট

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

আউটপুট

ব্যাখ্যা

সর্বোচ্চ যোগফলয়ুক্ত নিম্নমুখী সাবসিকোয়েন্স: {10, 5, 2} = 10 + 5 + 2 = 17

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং ব্যবহার করা হবে। maxSum[] অ্যারে তৈরি করব যা i-তম ইন্ডেক্স পর্যন্ত সর্বোচ্চ যোগফল সংরক্ষণ করবে। সূত্র:

maxSum[i] = arr[i] + max(maxSum[0 ... i-1]) (যেখানে arr[i] < arr[j])

সর্বোচ্চ যোগফল হবে maxSum[] অ্যারেতে সর্বোচ্চ মান।

উদাহরণ

#include <iostream>
using namespace std;
int findMaxSumDecSubSeq(int arr[], int N){
    int maximumSum = 0;
    int maxSum[N];
    for (int i = 0; i < N; i++)
        maxSum[i] = arr[i];
    for (int i = 1; i < N; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] < arr[j] && maxSum[i] < maxSum[j] + arr[i])
                maxSum[i] = maxSum[j] + arr[i];
    for (int i = 0; i < N; i++)
        if (maximumSum < maxSum[i])
            maximumSum = maxSum[i];
    return maximumSum;
}
int main(){
    int arr[] = { 5, 4, 100, 3, 2, 101, 1 };
    int N= sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum sum of decreasing subsequence is "<আউটপুট
The maximum sum of decreasing subsequence is 106