C++ में सबसे लंबे बिटोनिक उपअनुक्रम की लंबाई खोजने का प्रोग्राम

एक अनुक्रम को बिटोनिक कहा जाता है यदि यह पहले सख्ती से बढ़ता है और फिर सख्ती से घटता है। एक पूर्णतः बढ़ता या घटता अनुक्रम भी बिटोनिक माना जाता है।

उदाहरण के लिए, सरणी [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] के लिए सबसे लंबे बिटोनिक उपअनुक्रम की लंबाई 7 है।

समाधान दृष्टिकोण

हम दो सरणियों का उपयोग करते हैं:

• increasingSubSeq[i]: इंडेक्स i पर समाप्त होने वाले सबसे लंबे बढ़ते उपअनुक्रम की लंबाई।
• decreasingSubSeq[i]: इंडेक्स i से शुरू होने वाले सबसे लंबे घटते उपअनुक्रम की लंबाई।

एल्गोरिदम:

1. increasingSubSeq को 1 से आरंभ करें। प्रत्येक i के लिए, सभी j < i जांचें और अपडेट करें।
2. decreasingSubSeq को 1 से आरंभ करें। प्रत्येक i को पीछे से लें, सभी j > i जांचें और अपडेट करें।
3. प्रत्येक इंडेक्स i के लिए, बिटोनिक लंबाई = increasingSubSeq[i] + decreasingSubSeq[i] - 1।
4. अधिकतम मान वापस करें।

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 << longBitonicSub(arr, n);
    return 0;
}

इनपुट

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16

आउटपुट

7