दोहराया सबर्रे की अधिकतम लंबाई  


कठिनाई स्तर मध्यम
में अक्सर पूछा वास्तव में खरात Roblox
ऐरे द्विआधारी खोज गतिशील प्रोग्रामिंग hashing

समस्या में "दोहराया सबर्रे की अधिकतम लंबाई" हमने दो ऐरे और 1 ऐरे दिए हैं, आपका काम दोनों में दिखाई देने वाले उप-सरणी की अधिकतम लंबाई का पता लगाना है। सरणियों.

उदाहरण  

इनपुट:

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

आउटपुट:

3

स्पष्टीकरण:

क्योंकि उप-सरणी की अधिकतम लंबाई 3 और सामान्य सरणी है [3,2,1]

दोहराया सबर्रे की अधिकतम लंबाईपिन

कलन विधि  

  1. आउटपुट को 0 पर सेट करें।
  2. वास्तविक इनपुट सरणी की लंबाई से अधिक 1 लंबाई के साथ एक चर पूर्णांक सरणी घोषित करें।
  3. से शुरू सरणी का अंतिम सूचकांक यह देखें कि array1 [i] array2 [j] के बराबर है, अगर सही है तो val [i] [j] = val [i + 1] [j + 1] +1।
  4. जाँच करें कि क्या आउटपुट वैल [i] [j] से कम है तो आउटपुट = val [i] [j] करें।
  5. पूरे ऐरे से अलग करें और उन स्थितियों की जाँच करें, जिनसे हमें अधिकतम आउटपुट मिलता है।
  6. वापसी आउटपुट।

व्याख्या  

अपना आउटपुट प्राप्त करने के लिए, हमें कुछ सरल ट्रैवर्सिंग करने की आवश्यकता है। इसके लिए, हम आउटपुट को इनिशियलाइज़ करने जा रहे हैं। फिर हम 0-डी की घोषणा करेंगे मैट्रिक्स array1 और array2 की लंबाई से एक से अधिक की लंबाई।

हम सरणी के अंतिम सूचकांक से दोनों सरणियों को पीछे करने जा रहे हैं। इसलिए हम कुछ शर्तों की जांच करेंगे और परिणाम को आउटपुट में संग्रहीत करेंगे।

तो चलिए एक उदाहरण लेते हैं और आगे बढ़ते हैं।

उदाहरण

मान लीजिए कि एक सरणी है:

यह भी देखें
अधिकतम तीन स्टैक के सम सम संभावित योग का पता लगाएं

int array1 [] = {1,2,3,2,1};

int array2 [] = {3,2,1,4,7};

आउटपुट = 0;

  • i = 4, j = 4;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

आउटपुट = 0;

  • i = 4, j = 3;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

आउटपुट = 0;

  • i = 4, j = 2;

अगर array1 [i] == array2 [j] सही और वैध है तो [i] [j] = val [i + 1] [j + 1] +1

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

फिर जांचें कि क्या आउटपुट <val [i] [j] सही है और आउटपुट = 1 करें।

आउटपुट = 1;

  • i = 4, j = 1;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

  • i = 4, j = 0;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

  • i = 3, j = 4;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

  • i = 3, j = 3;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

  • i = 3, j = 2;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

  • i = 3, j = 1;

अगर array1 [i] == array2 [j] सही और वैध है तो [i] [j] = val [i + 1] [j + 1] +1

तब वैल [३] [१] = वैल [४] [२] + १ = २ तो वैल [३] [१] = २।

फिर जांचें कि क्या आउटपुट <val [i] [j] सही है और आउटपुट = val [i] [j] करें।

आउटपुट = 2;

  • i = 3, j = 0;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

  • i = 2, j = 4;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

  • i = 2, j = 3;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

  • i = 2, j = 2;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

  • i = 2, j = 1;

अगर array1 [i] == array2 [j] गलत है और कुछ भी करने वाला नहीं है।

  • i = 2, j = 0;

अगर array1 [i] == array2 [j] सही और वैध है तो [i] [j] = val [i + 1] [j + 1] +1

तब वैल [2] [0] = वैल [3] [1] + 1 = 2 + 1 फिर वैल [2] [0] = 3।

फिर जांचें कि क्या आउटपुट <val [i] [j] सही है और आउटपुट = val [2] [0] करें।

आउटपुट = 3;

और यह दोहराई गई सरणी की अधिकतम लंबाई होगी जो 3 है, भले ही हम ट्रैवर्सिंग में तत्वों को समान पाते हैं, लेकिन यह आउटपुट में अपडेशन नहीं करेगा, क्योंकि यह सबअरे नहीं होगा

आइए आइए = 1, जे = 1 पर हम अगले समान तत्व को खोजने वाले हैं ताकि यह वैल करेगा [1] [1] = वैल [2] [2] +1;

यह भी देखें
अनुक्रमों को बढ़ाने के लिए न्यूनतम स्वैप

और अगर हम आउटपुट की जांच करते हैं <val [1] [1] तो हर बार यह गलत है और कुछ भी नहीं करेगा।

तो यहाँ, आउटपुट 3 है।

कार्यान्वयन  

बार-बार की अधिकतम लंबाई के लिए C ++ प्रोग्राम

#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

दोहराया सबर्रे की अधिकतम लंबाई के लिए जटिलता विश्लेषण  

समय जटिलता

O (a × b) जहां 'ए' पहले सरणी का आकार है और "बी" दूसरे सरणी का आकार है।

अंतरिक्ष जटिलता

O (a × b) जहां 'ए' पहले सरणी का आकार है और "बी" दूसरे सरणी का आकार है।

संदर्भ