पुनरावृत्ती झालेल्या सबब्रेची कमाल लांबी  


अडचण पातळी मध्यम
वारंवार विचारले खरंच करात Roblox
अरे बायनरी शोध डायनॅमिक प्रोग्रामिंग हॅशिंग

“पुनरावृत्ती झालेल्या सबब्रेची कमाल लांबी” मध्ये आम्ही दोन अ‍ॅरे अ‍ॅरे 1 आणि अ‍ॅरे 2 दिले आहेत, आपले कार्य म्हणजे दोन्ही मधील उप-अ‍ॅरेची कमाल लांबी शोधणे अ‍ॅरे.

उदाहरण  

इनपुट:

[1,2,3,2,1]
[3,2,1,4,7]

आउटपुट:

3

स्पष्टीकरण:

कारण उप-अ‍ॅरेची कमाल लांबी 3 आहे आणि सामान्य अ‍ॅरे [3,2,1]

पुनरावृत्ती झालेल्या सबब्रेची कमाल लांबी

अल्गोरिदम  

  1. आउटपुट 0 वर सेट करा.
  2. वास्तविक इनपुट अ‍ॅरेच्या लांबीपेक्षा 1 लांबीसह चल पूर्णांक अ‍ॅरे घोषित करा.
  3. पासून प्रारंभ अ‍ॅरेची शेवटची अनुक्रमणिका अ‍ॅरे 1 [i] अ‍ॅरे 2 [जे] बरोबर असल्यास वॅल [i] [जे] = व्हॅल [आय + १] [जे + १] +१ बरोबर असल्याचे तपासा.
  4. आउटपुट व्हॅलपेक्षा कमी आहे का ते तपासा [i] [j] नंतर आउटपुट = व्हॉल [i] [जे] करा.
  5. संपूर्ण अ‍ॅरेवर परीक्षण करा आणि आम्हाला जास्तीत जास्त आउटपुट प्राप्त होण्यास अटी पहा.
  6. रिटर्न आउटपुट

स्पष्टीकरण  

आपले आऊटपुट मिळवण्यासाठी आम्हाला काही साधे ट्रॅव्हर्सिंग करणे आवश्यक आहे. त्यासाठी आउटपुट ० वर नेऊ. नंतर आपण २-डी घोषित करू मॅट्रिक्स अ‍ॅरे 1 आणि अ‍ॅरे 2 च्या लांबीपेक्षा आणखी एक लांबी.

अ‍ॅरेच्या शेवटच्या इंडेक्स मधून आपण दोन्ही अ‍ॅरे ओलांडणार आहोत. तर आपण काही कंडिशन्स तपासू आणि निकाल आउटपुट मध्ये संचित करू.

चला तर मग आपण एक उदाहरण घेऊ आणि पुढे जाऊया.

उदाहरण

समजा असे अ‍ॅरे आहेत:

इंट अ‍ॅरे 1 [] = {1,2,3,2,1};

इंट अ‍ॅरे 2 [] = {3,2,1,4,7};

आउटपुट = 0;

  • i = 4, j = 4;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

हे सुद्धा पहा
तीन स्टॅकचा जास्तीत जास्त संभाव्य समान बेरीज शोधा

आउटपुट = 0;

  • i = 4, j = 3;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

आउटपुट = 0;

  • i = 4, j = 2;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] सत्य आणि व्हॅल [i] [j] = व्हॅल [i + 1] [j + 1] +1 परत केल्यास

then val[4][2]=val[5][3]+1=1 then val[i][j]=1.

नंतर आउटपुट <व्हॅल [i] [जे] खरे परत येत असल्यास व आउटपुट = 1 करा.

आउटपुट = 1;

  • i = 4, j = 1;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

  • i = 4, j = 0;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

  • i = 3, j = 4;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

  • i = 3, j = 3;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

  • i = 3, j = 2;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

  • i = 3, j = 1;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] सत्य आणि व्हॅल [i] [j] = व्हॅल [i + 1] [j + 1] +1 परत केल्यास

नंतर व्हॅल [3] [1] = व्हॅल [4] [2] + 1 = 2 नंतर व्हॅल [3] [1] = 2.

नंतर आउटपुट <व्हॅल [i] [जे] खरे परत येत असल्यास व आउटपुट = व्हॅल [i] [जे] करत असल्याचे तपासा.

आउटपुट = 2;

  • i = 3, j = 0;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

  • i = 2, j = 4;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

  • i = 2, j = 3;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

  • i = 2, j = 2;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

  • i = 2, j = 1;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] चुकीचे परत आले आणि काहीही करणार नाही.

  • i = 2, j = 0;

अ‍ॅरे 1 [i] == अ‍ॅरे 2 [जे] सत्य आणि व्हॅल [i] [j] = व्हॅल [i + 1] [j + 1] +1 परत केल्यास

नंतर व्हॅल [2] [0] = व्हॅल [3] [1] + 1 = 2 + 1 नंतर व्हॅल [2] [0] = 3.

नंतर आउटपुट <व्हॅल [i] [जे] खरे परत येत असल्यास व आउटपुट = व्हॅल [२] [०] करत असल्याचे तपासा.

आउटपुट = 3;

आपल्याला पुनरावृत्ती होणार्‍या अ‍ॅरेची जास्तीत जास्त लांबी 3 असेल जरी आपल्याला ट्रॅव्हर्सिंगमध्ये घटक समान आढळले परंतु ते आउटपुटमध्ये अपडेटेड होणार नाही, कारण ती सबर्रे होणार नाही

i = 1, j = 1 वर असे सांगा की आम्हाला पुढील तत्सम घटक सापडतील जेणेकरून ते व्हॅल [1] [1] = व्हॅल [2] [2] +1 करेल;

आणि आम्ही आऊटपुट <वाल [1] [1] तपासल्यास प्रत्येक वेळी ते चुकीचे परत येते आणि काहीच करत नाही.

हे सुद्धा पहा
अनुक्रम वाढवण्यासाठी किमान स्वॅप

येथे आऊटपुट 3 आहे.

अंमलबजावणी  

पुनरावृत्ती झालेल्या सबब्रेच्या कमाल लांबीसाठी सी ++ प्रोग्राम

#include <iostream>
using namespace std;

int lengthOfRepeatedArray(int array1[], int array2[])
{
    int output = 0;
    int val[6][6]= {0};

    for (int i = 4; i >= 0; --i)
    {
        for (int j = 4; j >= 0; --j)
        {
            if (array1[i] == array2[j])
            {
                val[i][j] = val[i+1][j+1] + 1;
                if(output < val[i][j])
                {
                    output = val[i][j];
                }
            }
        }
    }
    return output;
}
int main()
{
    int a[]= {1,2,3,2,1};
    int b[]= {3,2,1,4,7};

    cout<<lengthOfRepeatedArray(a,b);
    return 0;
}
3

पुनरावृत्ती झालेल्या सुबर्रेच्या जास्तीत जास्त लांबीसाठी जावा प्रोग्राम

class repeatedArrayLength
{
    public static int lengthOfRepeatedArray(int[] array1, int[] array2)
    {
        int output = 0;
        int val[][] = new int[array1.length + 1][array2.length + 1];
        for (int i = array1.length - 1; i >= 0; --i)
        {
            for (int j = array2.length - 1; j >= 0; --j)
            {
                if (array1[i] == array2[j])
                {
                    val[i][j] = val[i+1][j+1] + 1;
                    if(output < val[i][j])
                        output = val[i][j];
                }
            }
        }
        return output;
    }
    public static void main(String []args)
    {
        int a[]= {1,2,3,2,1};
        int b[]= {3,2,1,4,7};
        System.out.println(lengthOfRepeatedArray(a,b));
    }
}
3

पुनरावृत्ती सुबर्रेच्या कमाल लांबीसाठी गुंतागुंत विश्लेषण  

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

ओ (अ × बी) जेथे "ए" पहिल्या अ‍ॅरेचा आकार आहे आणि “बी” दुसर्‍या अ‍ॅरेचा आकार आहे.

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

ओ (अ × बी) जेथे "ए" पहिल्या अ‍ॅरेचा आकार आहे आणि “बी” दुसर्‍या अ‍ॅरेचा आकार आहे.

संदर्भ