सर्वांत लांब बायटॉनिक उपखंड  


अडचण पातळी हार्ड
वारंवार विचारले कोडनेशन डीई शॉ Google जेपी मॉर्गन मायक्रोसॉफ्ट
अरे डायनॅमिक प्रोग्रामिंग

समजा आपल्याकडे एक आहे अॅरे of पूर्णांक, समस्या विधान सर्वात लांब बीटोनिक अनुक्रम शोधण्यासाठी विचारतो. अ‍ॅरेचा बिटोनिक अनुक्रम हा क्रम म्हणून ओळखला जातो जो प्रथम वाढतो आणि नंतर कमी होतो.

उदाहरण  

arr[] = {1,4,2,76,43,78,54,32,1,56,23}
7

स्पष्टीकरण

1 4 76 78 54 32 23 (प्रथम 78 पर्यंत वाढत आहे आणि नंतर 23 पर्यंत कमी होत आहेत.

सर्वांत लांब बायटॉनिक उपखंड

 

अल्गोरिदम  

  1. अ‍ॅरे घोषित करा वाढती सेक [] दिलेल्या अ‍ॅरे लांबीच्या लांबीइतकाच आकार.
  2. तयार केलेल्या अ‍ॅरे वाढणाe्यांपैकी 1 म्हणून सर्व निर्देशांक घटकांची सुरूवात करा [].
  3. डावीकडून उजवीकडे वाढणाS्या सेक [] मध्ये संचयित करून सर्वात मोठा वाढणारा उपक्रम शोधा.
  4. अ‍ॅरे घोषित करा कमी होत आहे [] दिलेल्या अ‍ॅरेच्या लांबीइतकाच आकार.
  5. उजवीकडून डावीकडे वरून कमी होत असलेल्या अनुक्रमात शोधा आणि त्यास कमी होत असलेल्या सेकमध्ये संचयित करा.
  6. मॅक्सऑटपुट नावाच्या व्हेरिएबलची सुरूवात वाढत्या सेक [०] + कमी होत असलेल्या सेक [०] - १ वर करा.
  7. कमाल शोधा वाढती सेक [i] + घटते सेक [i] - १ आणि मॅक्सऑटपुटमध्ये संचयित करा.
  8. परत करा कमाल आउटपुट.

स्पष्टीकरण

आकार n च्या इनपुट अ‍ॅरेमध्ये सकारात्मक पूर्णांक असतात. आम्हाला दिलेल्या अ‍ॅरेचा सर्वात लांब बीटोनिक क्रम शोधण्यास सांगितले जाते. बिटोनिक सीक्वेन्स ही अनुक्रम म्हणून परिभाषित केली जाऊ शकते जी प्रथम वाढते, म्हणजे अनुक्रमातील संख्या प्रथम वाढते. नंतर क्रम संपल्याशिवाय संख्या कमी होते. आम्हाला सर्वात लांब बिटोनिक अनुक्रमांची लांबी निश्चित करणे आवश्यक आहे.

हे सुद्धा पहा
मॅट्रिक्स डायग्नल सम लेटकोड सोल्यूशन

प्रथम, द्रावण दोन-भागांमध्ये विभक्त करा. आम्ही दोन अ‍ॅरे घोषित केल्या, पहिल्या अ‍ॅरेला एक मानले जाते वाढतीवेळ रचना. सर्वात मोठा वाढणारा क्रम हा एक क्रम आहे ज्यात संख्या वाढणार्‍या क्रमामध्ये प्रथम असावी. तर आपण नेस्टेड लूपमध्ये अ‍ॅरे ओलांडणार आहोत. वाढती अनुक्रम शोधत रहा. तर आपल्याला अशी अट तपासली पाहिजे की जर सध्याचा घटक पुढील घटकापेक्षा कमी असेल. आणि वाढती सेकचा वर्तमान घटक वाढणार्‍या सेकच्या पुढील घटकापेक्षा कमी आहे []. जर खरे असेल तर घटक वाढत्या सेक [j] + १ म्हणून संचित करा. हे जोडले जाईल कारण त्यात आधी आपण अ‍ॅरेला आधीच आरंभ केला आहे.

दुसरे, अ‍ॅरे घोषित करा. कमी होत आहे []. या कमी होणार्‍या सेक [] मध्ये, आपण अ‍ॅरेच्या उजवीकडून डावीकडे, नेस्टेड लूप फॅशनमध्ये अ‍ॅरे ओलांडणार आहोत. वर्तमान घटक पुढील घटकापेक्षा मोठा आहे की नाही हे आम्ही तपासणार आहोत. कारण आपण उजवीकडून डावीकडे फिरत आहोत. नंतर ते कमी होत असलेल्या सेक [i] वर कमी होत असलेल्या सेक [j] +1 वर अद्यतनित करा. कोडच्या शेवटच्या चरणात, आम्हाला जास्तीत जास्त वाढणारी सेक्स [i] + कमी होत जाणे [i] - 1 शोधणे आवश्यक आहे जे मॅक्सऑटपुटमध्ये संग्रहित आहे.

कोड  

प्रदीर्घ बिटोनिक उपसमर्थासाठी सी ++ कोड

#include<iostream>

using namespace std;

int BitonicSequence( int arr[], int n )
{
    int i, j;

    int *increasingSeq = new int[n];
    for (i = 0; i < n; i++)
        increasingSeq[i] = 1;

    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                increasingSeq[i] = increasingSeq[j] + 1;

    int *decreasingSeq = new int [n];
    for (i = 0; i < n; i++)
        decreasingSeq[i] = 1;

    for (i = n-2; i >= 0; i--)
        for (j = n-1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                decreasingSeq[i] = decreasingSeq[j] + 1;

    int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

    for (i = 1; i < n; i++)
        if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
            maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

    return maxOutput;

}
int main()
{
    int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Length of Longest Bitonic Sequence is "<< BitonicSequence(arr, n);
    return 0;
}
Length of Longest Bitonic Sequence is 7

प्रदीर्घ बिटोनिक उपसमर्थणासाठी जावा कोड

class longestBitonicSequence
{
    public static int BitonicSequence( int arr[], int n )
    {
        int i, j;

        int[] increasingSeq = new int[n];
        for (i = 0; i < n; i++)
            increasingSeq[i] = 1;

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                    increasingSeq[i] = increasingSeq[j] + 1;

        int[] decreasingSeq = new int [n];
        for (i = 0; i < n; i++)
            decreasingSeq[i] = 1;

        for (i = n-2; i >= 0; i--)
            for (j = n-1; j > i; j--)
                if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                    decreasingSeq[i] = decreasingSeq[j] + 1;


        int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

        for (i = 1; i < n; i++)
            if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
                maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

        return maxOutput;
    }

    public static void main (String[] args)
    {
        int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
        int n = arr.length;
        System.out.println("Length of longest bitonic sequence is "+ BitonicSequence( arr, n ));
    }
}
Length of longest bitonic sequence is 7

गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (एन2जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्ही नेस्टेड लूप वापरल्यामुळे अल्गोरिदम बहुपदीच्या काळात चालला.

हे सुद्धा पहा
के कामगारांसाठी किमान किंमत

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्ही दोन अतिरिक्त अ‍ॅरे वापरल्या आहेत ज्यांचा आकार इनपुट अ‍ॅरेवर अवलंबून आहे. जागेची जटिलता रेखीय आहे.