Қайталанатын ішкі массивтің максималды ұзындығы  


Күрделілік дәрежесі орта
Жиі кіреді шынында Карат Roblox
Array Екілік іздеу Динамикалық бағдарламалау Хэш

«Қайталанатын ішкі массивтің максималды ұзындығы» мәселесінде біз 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 [j] -ге тең екендігін тексеріңіз, егер шын болса val [i] [j] = val [i + 1] [j + 1] +1.
  4. Шығарылымның val [i] [j] -ден аз екенін тексеріп, output = val [i] [j] мәнін жасаңыз.
  5. Барлық массивті қайталаңыз және шарттарды тексеріңіз, біз максималды нәтижеге қол жеткіземіз.
  6. Шығуды қайтару.

Түсіндіру  

Біздің өнімімізді алу үшін, біз қарапайым траверинг жасауымыз керек. Ол үшін біз нәтижені 0-ге дейін инициализациялаймыз, содан кейін 2-өлшемді деп жариялаймыз Матрица ұзындығы массив1 мен жиым2 ұзындығынан бір артық.

Біз жиымның екі индексін де массивтің соңғы индексінен өтеміз. Сондықтан біз кейбір шарттарды тексеріп, нәтижені нәтижеге сақтаймыз.

Сонымен мысал алып, әрі қарай жалғастырайық.

мысал

Массив келесідей:

int массив1 [] = {1,2,3,2,1};

int массив2 [] = {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;

егер массив1 [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 болатынын тексеріңіз.

шығу = 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;

егер массив1 [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] шығысының шындыққа сәйкес келетіндігін және нәтиже = 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;

егер массив1 [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] шығысының шындыққа сәйкес келетіндігін тексеріп, output = val [2] [0] болуын тексеріңіз.

шығу = 3;

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

i = 1, j = 1 кезінде келесі ұқсас элементті табамыз, сонда ол val [1] [1] = val [2] [2] +1;

егер біз <val [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

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

Қайталанатын ішкі массивтің максималды ұзындығы бойынша күрделілікті талдау  

Уақыттың күрделілігі

O (a × b) қайда A - бұл бірінші массивтің өлшемі және «Б» - бұл екінші массивтің өлшемі.

Ғарыштың күрделілігі

O (a × b) қайда A - бұл бірінші массивтің өлшемі және «Б» - бұл екінші массивтің өлшемі.

анықтамалық