Максімальная даўжыня паўторнага падмасіва


Узровень складанасці серада
Часта пытаюцца ў Сапраўды Karat Roblox
масіў Двайковы пошук Дынамічнае праграмаванне хэшавання

У задачы "Максімальная даўжыня паўторнага падмасіва" мы далі два масівы Array 1 і Array 2, ваша задача знайсці максімальную даўжыню падмасіва, які з'яўляецца ў абодвух масівы.

Прыклад

Уваход:

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

Вынахад:

3

Тлумачэнне:

Паколькі максімальная даўжыня падмасіва роўная 3, а агульны масіў - [3,2,1]

Максімальная даўжыня паўторнага падмасіва

Алгарытм

  1. Усталюйце выхад на 0.
  2. Абвясціце зменны цэлалікавы масіў, даўжыня якога на 1 большая за даўжыню фактычнага ўваходнага масіва.
  3. Пачынаючы з апошні індэкс масіва праверыць, калі array1 [i] роўна array2 [j], калі true, 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};

выхад = 0;

  • i = 4, j = 4;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

выхад = 0;

  • i = 4, j = 3;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

выхад = 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] true і зрабіце output = 1.

выхад = 1;

  • i = 4, j = 1;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

  • i = 4, j = 0;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

  • i = 3, j = 4;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

  • i = 3, j = 3;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

  • i = 3, j = 2;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

  • 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] true і зрабіце output = val [i] [j].

выхад = 2;

  • i = 3, j = 0;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

  • i = 2, j = 4;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

  • i = 2, j = 3;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

  • i = 2, j = 2;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

  • i = 2, j = 1;

калі array1 [i] == array2 [j] вяртае false і нічога не збіраецца рабіць.

  • 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] true і зрабіце output = val [2] [0].

выхад = 3;

І гэта будзе максімальная даўжыня паўтаранага масіва, роўная 3, нават пасля таго, як мы знойдзем элементы, роўныя пры праходжанні, але гэта не будзе абнаўляць вывад, таму што гэта не будзе падмасівам

скажам, пры i = 1, j = 1 мы знойдзем наступны падобны элемент, каб ён зрабіў val [1] [1] = val [2] [2] +1;

і калі мы правяраем вывад <val [1] [1], то кожны раз, калі ён вяртае false і нічога не зробіць.

Такім чынам, выхад - 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

Праграма 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) дзе «А» - памер першага масіва і "Б" - памер другога масіва.

Касмічная складанасць

O (a × b) дзе «А» - памер першага масіва і "Б" - памер другога масіва.

Спасылка