लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस (LIS) एक ऐसा सबसीक्वेंस होता है जहां प्रत्येक एलिमेंट अपने पिछले एलिमेंट से बड़ा होता है।
यहां हम पूर्णांकों के एक सेट से लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस की लंबाई ढूंढने का प्रयास करेंगे।
इनपुट: पूर्णांकों का सेट {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
आउटपुट: लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस की लंबाई। यहां यह 6 है। सबसीक्वेंस है: 0, 2, 6, 9, 13, 15।
एल्गोरिदम
longestSubSeq(subarray, n)
इनपुट: सब ऐरे और सब ऐरे का आकार।
आउटपुट: लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस की लंबाई।
Begin
length नामक आकार n का ऐरे परिभाषित करें
शुरुआत में length के सभी एंट्रीज़ को 0 पर सेट करें
i := 1 से n-1 तक, करें
j := 0 से i-1 तक, करें
यदि subarray[j] < subarray[i] और length[j] > length[i], तो
length[i] := length[j]
किया
length[i] को 1 से बढ़ाएं
किया
lis := 0
i := 0 से n-1 तक, करें
lis := lis और length[i] का अधिकतम
किया
lis लौटाएं
End
उदाहरण कोड
#include <iostream>
using namespace std;
int longestSubSeq(int subArr[], int n) {
int length[n] = { 0 }; // सभी length को 0 पर सेट करें
length[0] = 1; // subArr[0] के साथ खत्म होने वाला सबसीक्वेंस 1 है
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
