सबसे लंबा बाइटोनिक सबसीक्वेंस

एक सीक्वेंस को बाइटोनिक कहा जाता है यदि वह पहले बढ़ता है और फिर घटता है। इस समस्या में, सभी धनात्मक पूर्णांकों का एक ऐरे दिया गया है। हमें एक ऐसा सबसीक्वेंस ढूंढना है जो पहले बढ़े और फिर घटे।

इस समस्या को हल करने के लिए, हम दो सबसीक्वेंस परिभाषित करेंगे: लॉन्गेस्ट इंक्रीजिंग सबसीक्वेंस (LIS) और लॉन्गेस्ट डिक्रीजिंग सबसीक्वेंस (LDS)। LIS ऐरे array[i] पर समाप्त होने वाले बढ़ते सबसीक्वेंस की लंबाई रखेगा। LDS ऐरे array[i] से शुरू होने वाले घटते सबसीक्वेंस की लंबाई स्टोर करेगा। इन दो ऐरे का उपयोग करके, हम सबसे लंबे बाइटोनिक सबसीक्वेंस की लंबाई प्राप्त कर सकते हैं।

इनपुट और आउटपुट

इनपुट: संख्याओं का एक सीक्वेंस
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

आउटपुट: सबसे लंबे बाइटोनिक सबसीक्वेंस की लंबाई। यहां यह 7 है।

एल्गोरिदम

longBitonicSub(array, size)

इनपुट: ऐरे, ऐरे का आकार
आउटपुट: सबसे लंबे बाइटोनिक सबसीक्वेंस की अधिकतम लंबाई

शुरुआत
    incSubSeq को ऐरे के आकार जितना परिभाषित करें
    शुरू में incSubSeq के सभी एंट्रीज़ को 1 से भरें
    i := 1 से size-1 तक, करें
        j := 0 से i-1 तक, करें
            यदि array[i] > array[j] और incSubSeq[i] < incSubSeq[j] + 1, तो
                incSubSeq[i] := incSubSeq[j] + 1
        पूर्ण
    पूर्ण
    decSubSeq को ऐरे के आकार जितना परिभाषित करें
    शुरू में decSubSeq के सभी एंट्रीज़ को 1 से भरें
    i := size-2 से 0 तक नीचे, करें
        j := size-1 से i+1 तक नीचे, करें
            यदि array[i] > array[j] और decSubSeq[i] < decSubSeq[j] + 1, तो
                decSubSeq[i] := decSubSeq[j] + 1
        पूर्ण
    पूर्ण
    max := incSubSeq[0] + decSubSeq[0] - 1
    i := 1 से size तक, करें
        यदि incSubSeq[i] + decSubSeq[i] - 1 > max, तो
            max := incSubSeq[i] + decSubSeq[i] - 1
    पूर्ण
    वापस max
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int longBitonicSub(int arr[], int size) {
    int *increasingSubSeq = new int[size];
    for (int i = 0; i < size; i++)
        increasingSubSeq[i] = 1;
    
    for (int i = 1; i < size; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSubSeq[i] < increasingSubSeq[j] + 1)
                increasingSubSeq[i] = increasingSubSeq[j] + 1;
    
    int *decreasingSubSeq = new int[size];
    for (int i = 0; i < size; i++)
        decreasingSubSeq[i] = 1;
    
    for (int i = size-2; i >= 0; i--)
        for (int j = size-1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSubSeq[i] < decreasingSubSeq[j] + 1)
                decreasingSubSeq[i] = decreasingSubSeq[j] + 1;
    
    int max = increasingSubSeq[0] + decreasingSubSeq[0] - 1;
    for (int i = 1; i < size; i++)
        if (increasingSubSeq[i] + decreasingSubSeq[i] - 1 > max)
            max = increasingSubSeq[i] + decreasingSubSeq[i] - 1;
    
    return max;
}

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 bitonic subsequence is " << longBitonicSub(arr, n);
}

आउटपुट

Length of longest bitonic subsequence is 7