सब भन्दा लामो Bitonic उपखंड  


कठिनाई तह हार्ड
बारम्बार सोधिन्छ CodeNation डे श गुगल जेपी मोर्गन माइक्रोसफ्ट
एरे डायनामिक प्रोग्रामिंग

मानौं तपाईंसँग एक छ array of पूर्णांक, समस्या कथन सबैभन्दा लामो बिटोनिक अनुक्रम पत्ता लगाउन सोध्दछ। एर्रेको बिटोनिक अनुक्रमलाई क्रमको रूपमा मानिन्छ जुन पहिले बढ्छ र त्यसपछि घट्छ।

उदाहरणका  

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

स्पष्टीकरण

1 4 76 78 54 32 २ ((पहिले 23 78 सम्म बढ्दै र २ 23 सम्म घट्दै।

सब भन्दा लामो Bitonic उपखंडपिन

 

अल्गोरिदम  

  1. एर्रे घोषित गर्नुहोस् बढ्दो सेक [] दिइएको एरे लम्बाई को आकार को जस्तै।
  2. सबै सूचकांक तत्वहरू सुरू एरे बृद्धि गर्ने १ को रूपमा सुरू गर्नुहोस् []।
  3. बायाँ देखि दाँया बढ्दो सेक् [[] मा भण्डार गरेर सबैभन्दा लामो बढ्दो अनुक्रमणिका पत्ता लगाउनुहोस्।
  4. एर्रे घोषित गर्नुहोस् घट्ने सेक [] दिइएको एर्रेको लम्बाइ जस्तो आकारको।
  5. दाँया देखि बाँया र घट्नेसेक [] मा भण्डारण गरेर सबैभन्दा लामो घट्ने अनुक्रम फेला पार्नुहोस्।
  6. म्याक्सआउटपुट भनिने भ्यारीएबल शुरुवात गर्नुहोस् बढ्दो सेकेक [०] + घटती सेक् [०] - १ मा।
  7. अधिकतम पत्ता लगाउनुहोस् बढ्दो सेक [i] + घट्दै सेक् [i] - १ र यसलाई मक्सआउटपुटमा भण्डार गर्नुहोस्।
  8. फिर्ता अधिकतम आउटपुट.

स्पष्टीकरण

आकार n को इनपुट एर्रेमा सकारात्मक पूर्णांकहरू हुन्छन्। हामीलाई दिइएको एर्रेको सबैभन्दा लामो बिटोनिक अनुक्रम पत्ता लगाउन भनियो। बिटोनिक अनुक्रमलाई अनुक्रमको रूपमा परिभाषित गर्न सकिन्छ जुन पहिले बढ्दछ, जसको अर्थ अनुक्रममा नम्बर पहिलो वृद्धि हुन्छ। तब क्रम क्रमको अन्त्य सम्म संख्या घट्छ। हामीले सबैभन्दा लामो बिटोनिक अनुक्रमको लम्बाई निर्धारित गर्नु पर्छ।

पनि हेर्नुहोस्
म्याट्रिक्स डायग्नल सम Leetcode समाधान

पहिले, समाधानलाई दुई-भागहरूमा छुट्याउनुहोस्। हामी दुई एर्रे घोषित गर्छौं, पहिलो एरे a को रूपमा मानिन्छ बढ्दो सेक् एर्रे। सब भन्दा लामो बढ्दो अनुक्रम भनेको अनुक्रम हो जसमा संख्याहरू बढ्दो क्रममा पहिलो हुनुपर्दछ। त्यसोभए, हामी नेस्ट गरिएको लुपमा एर्रे पार गर्न जाँदैछौं। बढ्दो अनुक्रमणिका फेला पार्न जारी राख्नुहोस्। त्यसो भए हामीले एउटा सर्त जाँच गर्नु पर्छ यदि हालको एलिमेन्ट अर्को एलिमेन्ट भन्दा कम छ भने। र साथै बढ्दो सेकको वर्तमान तत्त्व बढ्दो सेक्कको अर्को तत्व भन्दा कम छ []। यदि सहि छ भने तत्त्वलाई बढ्दो सेक्क [j] + १ को रूपमा भण्डार गर्नुहोस्। यसले थप गर्दछ किनकि हामीले यसमा एरे पहिले नै आरम्भ गरिसकेका छौं।

दोस्रो, एर्रे घोषित गर्नुहोस्, कम हुँदैछ [[। यस घट्दो सेक [] मा हामी एरेलाई नेस्टेड लूप फेसनमा जाँदै छौं, एर्रेको दायाँबाट बाँया। हामी हालको एलिमेन्ट अर्को एलिमेन्ट भन्दा ठूलो छ कि छैन जाँच्ने छौं। किनकि हामी दायाँबाट बाँया हिंडिरहेका छौं। त्यसो भए यसलाई घट्ने सेकेक [i] लाई घट्ने सेकेक [j] +१ मा अपडेट गर्नुहोस्। कोडको अन्तिम चरणमा, हामीले अधिकतम सेक्स् खोज्नु पर्छ [i] + घट्ने सेक्स [i] - १ जुन मक्सआउटपुटमा भण्डार गरिएको छ।

कोड  

C ++ कोड सबैभन्दा लामो Bitonic उप अनुक्रमको लागि

#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

सबै भन्दा लामो Bitonic उप अनुक्रमको लागि जाभा कोड

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

जटिलता विश्लेषण  

समय जटिलता

O (n2जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। हामीले नेस्टेड लूप प्रयोग गर्यौं जसले एल्गोरिथ्मलाई बहुपद समयमा चलाउँदछ।

पनि हेर्नुहोस्
K कामदारहरूलाई भाडामा लिन न्यूनतम लागत

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। हामीले दुई थप एर्रेहरू प्रयोग गरेका छौं जसको आकार इनपुट एर्रेमा निर्भर छ। ठाउँ जटिलता रैखिक छ।