সর্বোচ্চ ক্রমবর্ধমান সাবসিকোয়েন্স (LIS)

সর্বোচ্চ ক্রমবর্ধমান সাবসিকোয়েন্স হল এমন একটি সাবসিকোয়েন্স যেখানে প্রতিটি উপাদান তার পূর্ববর্তী উপাদানের চেয়ে বড়। এখানে আমরা একটি পূর্ণসংখ্যা সেট থেকে সর্বোচ্চ ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য খুঁজে বের করব।

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

ইনপুট: পূর্ণসংখ্যার একটি সেট।
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

আউটপুট: সর্বোচ্চ ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য। এখানে এটি ৬।
সাবসিকোয়েন্স: 0, 2, 6, 9, 13, 15

অ্যালগরিদম

longestSubSeq(subarray, n)

ইনপুট: সাব অ্যারে এবং এর আকার।
আউটপুট: সর্বোচ্চ ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য।

শুরু
  length নামক n আকারের অ্যারে সংজ্ঞায়িত করুন
  length এর সকল এন্ট্রি ০ দিয়ে শুরু করুন
  i := 1 থেকে n-1 পর্যন্ত, করুন
    j := 0 থেকে i-1 পর্যন্ত, করুন
      যদি subarray[j] < subarray[i] এবং length[j] > length[i] হয়, তবে
        length[i] := length[j]
    শেষ
    length[i] ১ দ্বারা বৃদ্ধি করুন
  শেষ
  lis := 0
  i := 0 থেকে n-1 পর্যন্ত, করুন
    lis := lis এবং length[i] এর মধ্যে সর্বোচ্চ
  শেষ
  lis ফেরত দিন
শেষ

উদাহরণ (C++)

#include <iostream>
using namespace std;

int longestSubSeq(int subArr[], int n) {
  int length[n] = { 0 };
  length[0] = 1;

  for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (subArr[j] < subArr[i] && length[j] > length[i])
        length[i] = length[j];
    }
    length[i]++;
  }

  int lis = 0;
  for (int i = 0; i < n; i++)
    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