Кайталанган субаррайдын максималдуу узундугу


Кыйынчылык деңгээли орто
Көп суралган Чындыгында Карат Roblox
согуштук тизме Binary Search Динамикалык программалоо Hashing

"Кайталанган субарряддын максималдуу узундугу" көйгөйүндө биз 1 массив жана 2 массив эки массивин бердик, сиздин милдетиңиз, эки массивде пайда болгон суб-массивдин максималдуу узундугун табуу. Arrays.

мисал

киргизүү:

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

Output:

3

Explanation:

Себеби суб-массивдин максималдуу узундугу 3, ал эми жалпы массив [3,2,1]

Кайталанган субаррайдын максималдуу узундугу

Algorithm

  1. Чыгууну 0 деп койду.
  2. Узундугу 1 болгон узундуктагы бүтүндөй массивди, чыныгы киргизилген массивдин узундугунан көбүрөөк жарыялаңыз.
  3. Баштап массивдин акыркы индекси 1 [i] массивинин 2 [j] массивине барабар экендигин текшериңиз, эгер чын болсо val [i] [j] = val [i + 1] [j + 1] +1.
  4. Чыгыш val [i] [j] дан аз экендигин текшерип, анда output = val [i] [j] кылыңыз.
  5. Бүткүл массивди кайталап, шарттарды текшерип, максималдуу натыйжа алабыз.
  6. Чыгууну кайтаруу.

түшүндүрүү

Биздин продукцияны алуу үчүн, биз жөнөкөй өтмөктөрдү жасашыбыз керек. Бул үчүн, биз чыгарууну 0го чейин баштайбыз, андан кийин 2-D деп жарыялайбыз Булакта узундугу 1 жана 2 массивинин узундугунан бир ашык.

Биз массивдин акыркы индексинен эки массивди тең тебебиз. Ошентип, биз кээ бир шарттарды текшерип, натыйжада натыйжаны сактайбыз.

Ошентип, бир мисал алып, андан ары уланта берели.

мисал

Массив төмөнкүдөй болсо дейли:

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

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

output = 0;

  • i = 4, j = 4;

array1 [i] == array2 [j] жалганды кайтарса жана эч нерсе кылбайм.

output = 0;

  • i = 4, j = 3;

array1 [i] == array2 [j] жалганды кайтарса жана эч нерсе кылбайм.

output = 0;

  • i = 4, j = 2;

array1 [i] == array2 [j] true жана 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 болгондугун текшериңиз.

output = 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] true жана val [i] [j] = val [i + 1] [j + 1] +1

анда val [3] [1] = val [4] [2] + 1 = 2 анда val [3] [1] = 2.

андан кийин <val [i] [j] натыйжасы чын болуп кайтып жаткандыгын текшерип, output = val [i] [j] кылыңыз.

output = 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] true жана 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] экендигин текшерип чыгыңыз.

output = 3;

Жана бул кайталанган массивдин максималдуу узундугу, биз элементтерди траизерде бирдей тапкандан кийин да 3кө барабар болот, бирок ал чыгарылышта жаңыланууну жасабайт, анткени бул субарра болбойт

i = 1, j = 1 болгондо, кийинки окшош элементти табабыз, ошондо val [1] [1] = val [2] [2] +1;

эгерде биз <val [1] [1] натыйжасын текшерсек, анда ал ар дайым жалган болуп, эч нерсе кылбайт.

Ошентип, бул жерде, чыгуу 3 болуп саналат.

ишке ашыруу

Кайра кайталанган subarray максималдуу узундугу үчүн 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

Кайталанган субаррайдын максималдуу узундугу үчүн Java программасы

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

Кайра кайталанган subarray максималдуу узундугу үчүн татаалдыгын талдоо

Убакыт татаалдыгы

O (a × b) кайда "A" биринчи массивдин көлөмү жана "B" экинчи массивдин көлөмү.

Космостун татаалдыгы

O (a × b) кайда "A" биринчи массивдин көлөмү жана "B" экинчи массивдин көлөмү.

шилтеме