सबसे लंबा बढ़ता हुआ सबसीक्वेंस

सबसे लंबा बढ़ता हुआ सबसीक्वेंस (LIS) एक ऐसा सबसीक्वेंस है जहां प्रत्येक आइटम अपने पिछले आइटम से बड़ा होता है। यहां हम पूर्णांकों के एक सेट से 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)

इनपुट: सब ऐरे और सब ऐरे का आकार
आउटपुट: सबसे लंबे बढ़ते सबसीक्वेंस की लंबाई

शुरुआत
    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 वापस करें
अंत

उदाहरण (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