الحد الأقصى لطول المصفوفة الفرعية المتكررة


مستوى الصعوبة متوسط
كثيرا ما يطلب في في الواقع قيراط Roblox
مجموعة بحث ثنائي البرمجة الديناميكية تجزئة

في مشكلة "الحد الأقصى لطول المصفوفة الفرعية المتكررة" قدمنا ​​مصفوفتين للصفيف 1 والصفيف 2 ، تتمثل مهمتك في العثور على الحد الأقصى لطول المصفوفة الفرعية التي تظهر في كل من المصفوفات.

مثال

الإدخال:

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

الإخراج:

3

التفسير:

لأن الحد الأقصى لطول المصفوفة الفرعية هو 3 والمصفوفة الشائعة هي [3,2,1،XNUMX،XNUMX]

الحد الأقصى لطول المصفوفة الفرعية المتكررة

خوارزمية

  1. اضبط الإخراج على 0.
  2. قم بتعريف مصفوفة عدد صحيح متغير بطول 1 أكبر من طول صفيف الإدخال الفعلي.
  3. بدءا من الفهرس الأخير للمصفوفة تحقق مما إذا كانت array1 [i] تساوي array2 [j] ، وإذا كانت صحيحة ، فإن val [i] [j] = val [i + 1] [j + 1] +1.
  4. تحقق مما إذا كان الإخراج أقل من val [i] [j] ثم قم بعمل الإخراج = val [i] [j].
  5. كرر على المصفوفة بأكملها وتحقق من الشروط نحصل على أقصى إخراج.
  6. عودة الإخراج.

تفسير

للحصول على مخرجاتنا ، نحتاج إلى بعض العبور البسيط. لهذا ، سنقوم بتهيئة الإخراج إلى 0. ثم سنعلن عن 2-D البخور بطول واحد أكبر من طول المصفوفة 1 والمصفوفة 2.

سنقوم باجتياز كلا المصفوفتين من الفهرس الأخير للصفيف. لذلك سوف نتحقق من بعض الشروط ونخزن النتيجة في الإخراج.

لذلك دعونا نأخذ مثالا ونمضي أبعد من ذلك.

مثال

لنفترض وجود مصفوفة على النحو التالي:

مجموعة int array1 [] = {1,2,3,2,1،XNUMX،XNUMX،XNUMX،XNUMX} ؛

مجموعة int array2 [] = {3,2,1,4,7،XNUMX،XNUMX،XNUMX،XNUMX} ؛

الإخراج = 0 ؛

  • أنا = 4 ، ي = 4 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

الإخراج = 0 ؛

  • أنا = 4 ، ي = 3 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

الإخراج = 0 ؛

  • أنا = 4 ، ي = 2 ؛

إذا كانت array1 [i] == array2 [j] تُرجع صحيحًا و val [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 ؛

  • أنا = 4 ، ي = 1 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

  • أنا = 4 ، ي = 0 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

  • أنا = 3 ، ي = 4 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

  • أنا = 3 ، ي = 3 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

  • أنا = 3 ، ي = 2 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

  • أنا = 3 ، ي = 1 ؛

إذا كانت array1 [i] == array2 [j] تُرجع صحيحًا و val [i] [j] = val [i + 1] [j + 1] +1

ثم val [3] [1] = val [4] [2] + 1 = 2 ثم val [3] [1] = 2.

ثم تحقق مما إذا كان الإخراج <val [i] [j] يعود صحيحًا ويقوم بإخراج = val [i] [j].

الإخراج = 2 ؛

  • أنا = 3 ، ي = 0 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

  • أنا = 2 ، ي = 4 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

  • أنا = 2 ، ي = 3 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

  • أنا = 2 ، ي = 2 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

  • أنا = 2 ، ي = 1 ؛

إذا كانت array1 [i] == array2 [j] ترجع خطأً ولن تفعل شيئًا.

  • أنا = 2 ، ي = 0 ؛

إذا كانت array1 [i] == array2 [j] تُرجع صحيحًا و val [i] [j] = val [i + 1] [j + 1] +1

ثم val [2] [0] = val [3] [1] + 1 = 2 + 1 ثم val [2] [0] = 3.

ثم تحقق مما إذا كان الإخراج <val [i] [j] يعود صحيحًا ونفّذ الإخراج = val [2] [0].

الإخراج = 3 ؛

وسيكون هذا هو الحد الأقصى لطول المصفوفة المكررة وهو 3 حتى بعد أن نجد العناصر متساوية في العبور لكنها لن تقوم بالتحديث في الإخراج ، لأن ذلك لن يكون المصفوفة الفرعية

لنفترض أنه عند i = 1 ، j = 1 سنجد العنصر المماثل التالي لذلك سيفعل val [1] [1] = val [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" هو حجم المصفوفة الأولى و "ب" هو حجم المصفوفة الثانية.

تعقيد الفضاء

O (أ × ب) أين "A" هو حجم المصفوفة الأولى و "ب" هو حجم المصفوفة الثانية.

الرقم المرجعي