লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স (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-র সব এন্ট্রি ০ দিয়ে ইনিশিয়ালাইজ করুন
for i := 1 to n-1, করুন
for j := 0 to i-1, করুন
if subarray[j] < subarray[i] এবং length[j] > length[i], তবে
length[i] := length[j]
লুপ শেষ
length[i] ১ বাড়ান
লুপ শেষ
lis := 0
for i := 0 to n-1, করুন
lis := lis এবং length[i]-র ম্যাক্সিমাম
লুপ শেষ
return lis
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
int longestSubSeq(int subArr[], int n) {
int length[n] = { 0 }; // সব length ০ সেট
length[0] = 1; // subArr[0] দিয়ে শেষ হওয়া সাবসিকোয়েন্স ১
for (int i = 1; i < n; i++) {
// প্রথম ক্যারেক্টার বাদ দিয়ে দ্বিতীয় থেকে সব
for (int j = 0; j < i; j++) {
// subArr[j] দিয়ে শেষ হওয়া সাবসিকোয়েন্স
if (subArr[j] < subArr[i] && length[j] > length[i])
length[i] = length[j];
}
length[i]++; // arr[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
