একটি প্রদত্ত সিকোয়েন্সের দীর্ঘতম ক্রমবর্ধমান অনুক্রম খুঁজে পেতে C++ প্রোগ্রাম

দীর্ঘতম ক্রমবর্ধমান অনুবর্তন হল একটি অনুগামী যেখানে একটি আইটেম তার আগের আইটেমের থেকে বড়।

এখানে আমরা পূর্ণসংখ্যার সেট থেকে দীর্ঘতম ক্রমবর্ধমান পরবর্তী দৈর্ঘ্য খুঁজে বের করার চেষ্টা করব।

Input: A set of integers. {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Output: The length of longest increasing subsequence. Here it is 6.
The subsequence is 0, 2, 6, 9, 13, 15.

অ্যালগরিদম

দীর্ঘতম সাবসেক(সাবরে, n)

ইনপুট :সাব অ্যারে এবং সাব অ্যারের আকার৷

আউটপুট :দীর্ঘতম ক্রমবর্ধমান সাব সিকোয়েন্স দৈর্ঘ্য।

Begin
   define array length of size n
   initially set 0 to all entries of length
      for i := 1 to n-1, do
         for j := 0 to i-1, do
            if subarray[j] < subarray[i] and length[j] > length[i], then
               length[i] := length[j]
      done
      increase length[i] by 1
   done
   lis := 0
   for i := 0 to n-1, do
      lis := maximum of lis and length[i]
   done
   return lis
End

উদাহরণ কোড

#include <iostream>
using namespace std;
int longestSubSeq(int subArr[], int n) {
   int length[n] = { 0 }; //set all length to 0
   length[0] = 1;    //subsequence ending with subArr[0] is 1
   for (int i = 1; i < n; i++) {    //ignore first character, second to all
      for (int j = 0; j < i; j++) {    //subsequence ends with subArr[j]
         if (subArr[j] < subArr[i] && length[j] > length[i])
            length[i] = length[j];
      }
      length[i]++; //add arr[i]
   }
   int lis = 0;
   for (int i = 0; i<n; i++) // find longest increasing subsequence
      lis = max(lis, length[i]);
   return lis;
}
int main() {
   int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
   int n = 16;
   cout << "Length of Longest Increasing Subsequence is: " << longestSubSeq(arr, n);
   return 0;
}

আউটপুট

Length of Longest Increasing Subsequence is: 6