এই সমস্যায়, আমাদেরকে N পূর্ণসংখ্যার একটি অ্যারে [] দেওয়া হয়েছে। আমাদের কাজ হল C++ তে সর্বাধিক সমষ্টি হ্রাসকারী অনুক্রম খুঁজে পাওয়া।
সমস্যা বর্ণনা
আমরা অ্যারে থেকে উপাদানগুলির সর্বাধিক যোগফল খুঁজে পাব যাতে পরবর্তীটি কঠোরভাবে হ্রাস পায়৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {3, 1, 6, 10, 5, 2, 9} আউটপুট
17
ব্যাখ্যা
সর্বাধিক যোগফল সহ পরবর্তী অনুক্রম হ'ল {10, 5, 2} =10 + 5 + 2 =17
সমাধান পদ্ধতি
এখানে, আমরা সমাধান খুঁজতে ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব। এখানে, আমরা একটি maxSum[] অ্যারে তৈরি করব যা সূচক i পর্যন্ত maxSum সংরক্ষণ করবে। ফলো সূত্রটি অ্যারে মান খুঁজে পেতে নিযুক্ত করা হয়,
maxSum[i] =arr[i] + max(maxSum[0 … (*i-1)])
সর্বাধিক যোগফল অ্যারের সর্বাধিক উপাদান দ্বারা দেওয়া হয় 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 "<<findMaxSumDecSubSeq(arr, N);
return 0;
} আউটপুট
The maximum sum of decreasing subsequence is 106
