Максимална дужина поновљеног низа


Ниво тешкоће Средњи
Често питани у Заиста карат роблок
Ред Бинарна претрага Динамичко програмирање Хасхинг

У проблему „Максимална дужина поновљеног подниза“ дали смо два низа Низ 1 и Низ 2, ваш задатак је да пронађете максималну дужину низа који се појављује у оба поља низови.

Пример

Улаз:

[КСНУМКС]
[КСНУМКС]

Излаз:

3

objašnjenje:

Будући да је максимална дужина под-низа 3, а заједнички низ [3,2,1]

Максимална дужина поновљеног низа

Алгоритам

  1. Поставите излаз на 0.
  2. Декларишите променљиви целобројни низ дужине 1 већи од дужине стварног улазног низа.
  3. Полазећи од последњи индекс низа проверите да ли је низ1 [и] једнак низу2 [ј], ако је тачно, онда је вал [и] [ј] = вал [и + 1] [ј + 1] +1.
  4. Проверите да ли је излаз мањи од вал [и] [ј], а затим учините оутпут = вал [и] [ј].
  5. Прелистајте читав низ и проверите услове да бисмо добили максималан излаз.
  6. Повратни излаз.

Објашњење

Да бисмо добили излаз, потребно је да обавимо једно једноставно прелажење. За ово ћемо иницијализовати излаз на 0. Тада ћемо прогласити 2-Д матрица дужине један више од дужине низа1 и низа2.

Прећи ћемо оба низа из последњег индекса низа. Тако ћемо проверити неке од услова и сачувати резултат у излазу.

Узмимо пример и наставимо даље.

Пример

Претпоставимо да имате низ као:

инт низ1 [] = {1,2,3,2,1};

инт низ2 [] = {3,2,1,4,7};

излаз = 0;

  • и = 4, ј = 4;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

излаз = 0;

  • и = 4, ј = 3;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

излаз = 0;

  • и = 4, ј = 2;

ако арраи1 [и] == арраи2 [ј] враћа труе и вал [и] [ј] = вал [и + 1] [ј + 1] +1

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

затим проверите да ли излаз <вал [и] [ј] враћа труе и да ли је оутпут = 1.

излаз = 1;

  • и = 4, ј = 1;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

  • и = 4, ј = 0;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

  • и = 3, ј = 4;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

  • и = 3, ј = 3;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

  • и = 3, ј = 2;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

  • и = 3, ј = 1;

ако арраи1 [и] == арраи2 [ј] враћа труе и вал [и] [ј] = вал [и + 1] [ј + 1] +1

тада вал [3] [1] = вал [4] [2] + 1 = 2 онда вал [3] [1] = 2.

затим проверите да ли излаз <вал [и] [ј] враћа труе и учините оутпут = вал [и] [ј].

излаз = 2;

  • и = 3, ј = 0;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

  • и = 2, ј = 4;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

  • и = 2, ј = 3;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

  • и = 2, ј = 2;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

  • и = 2, ј = 1;

ако арраи1 [и] == арраи2 [ј] врати фалсе и неће учинити ништа.

  • и = 2, ј = 0;

ако арраи1 [и] == арраи2 [ј] враћа труе и вал [и] [ј] = вал [и + 1] [ј + 1] +1

онда вал [2] [0] = вал [3] [1] + 1 = 2 + 1 онда вал [2] [0] = 3.

затим проверите да ли излаз <вал [и] [ј] враћа труе и учините оутпут = вал [2] [0].

излаз = 3;

А ово ће бити максимална дужина поновљеног низа која је 3 чак и након што пронађемо елементе једнаке у преласку, али то неће извршити надоградњу у излазу, јер то неће бити подред

рецимо да ћемо при и = 1, ј = 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

Анализа сложености за максималну дужину поновљеног подниза

Сложеност времена

О (а × б) где "А" је величина првог низа и „Б“ је величина другог низа.

Сложеност простора

О (а × б) где "А" је величина првог низа и „Б“ је величина другог низа.

Препорука