সর্বাধিক যোগফল পরবর্তী ক্রমবর্ধমান

সর্বোচ্চ যোগফল ক্রমবর্ধমান অনুক্রম হল একটি প্রদত্ত পূর্ণসংখ্যার তালিকার একটি অনুগামী, যার যোগফল সর্বাধিক এবং পরবর্তীতে, সমস্ত উপাদান ক্রমবর্ধমান ক্রমে সাজানো হয়৷

সর্বাধিক যোগফল ক্রমবর্ধমান অনুগামী সঞ্চয় করার জন্য একটি অ্যারে আছে, যেমন L[i] হল সর্বাধিক যোগফল বৃদ্ধির অনুগামী, যা অ্যারে[i] দিয়ে শেষ হচ্ছে।

ইনপুট এবং আউটপুট

Input:
Sequence of integers. {3, 2, 6, 4, 5, 1}
Output:
Increasing subsequence whose sum is maximum. {3, 4, 5}.

অ্যালগরিদম

maxSumSubSeq(array, n)

ইনপুট: সংখ্যার ক্রম, উপাদানের সংখ্যা।

আউটপুট: ক্রমবর্ধমান সাব সিকোয়েন্সের সর্বোচ্চ যোগফল।

Begin
   define array of arrays named subSeqLen of size n.
   add arr[0] into the subSeqLen
   for i in  range (1 to n-1), do
      for j in range (0 to i-1), do
         if arr[i] > arr[j] and sum of subSeqLen [i] < sum of subSeqLen [j], then
            subSeqLen[i] := subSeqLen[j]
      done
   done

   add arr[i] into subSeqLen[i]
   res := subSeqLen[0]
           
   for all values of subSeqLen, do
      if sum of subSeqLen[i] > sum of subSeqLen[res], then
         res := subSeqLen[i]
   done

   print the values of res.

End

উদাহরণ

#include <iostream>
#include <vector>
using namespace std;
 
int findAllSum(vector<int> arr) {    //find sum of all vector elements
   int sum = 0;

   for(int i = 0; i<arr.size(); i++) {
      sum += arr[i];
   }

   return sum;
}
 
void maxSumSubSeq(int arr[], int n) {
   vector <vector<int> > subSeqLen(n);    //max sum increasing subsequence ending with arr[i]
   subSeqLen[0].push_back(arr[0]);

   for (int i = 1; i < n; i++) {         //from index 1 to all
      for (int j = 0; j < i; j++) {     //for all j, j<i
           
         if ((arr[i] > arr[j]) && (findAllSum(subSeqLen[i]) < findAllSum(subSeqLen[j])))
            subSeqLen[i] = subSeqLen[j];
      }
       
      subSeqLen[i].push_back(arr[i]);    //sub Sequence ends with arr[i]
   }
 
   vector<int> res = subSeqLen[0];
 
   for(int i = 0; i<subSeqLen.size(); i++) {
      if (findAllSum(subSeqLen[i]) > findAllSum(res))
         res = subSeqLen[i];
   }

   for(int i = 0; i<res.size(); i++)
      cout << res[i] << " ";
   cout << endl;
}

int main() {
   int arr[] = { 3, 2, 6, 4, 5, 1 };
   int n = 6;
   cout << "The Maximum Sum Subsequence is: ";
   maxSumSubSeq(arr, n);
}

আউটপুট

The Maximum Sum Subsequence is: 3 4 5