Максимальная длина повторяемого подмассива


Сложный уровень средний
Часто спрашивают в В самом деле карат Roblox
массив Бинарный поиск Динамическое программирование хеширования

В задаче «Максимальная длина повторяющегося подмассива» мы дали два массива: массив 1 и массив 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. Убедитесь, что output меньше val [i] [j], затем выполните output = val [i] [j].
  5. Перебирая весь массив и проверяя условия, мы получаем максимальный результат.
  6. Возврат вывода.

объяснение

Чтобы получить результат, нам нужно проделать простой обход. Для этого мы собираемся инициализировать вывод равным 0. Затем мы объявим 2-D матрица длины на единицу больше, чем длина array1 и array2.

Мы собираемся пройти по обоим массивам, начиная с последнего индекса массива. Поэтому мы проверим некоторые условия и сохраним результат в выводе.

Итак, давайте возьмем пример и продолжим.

Пример

Предположим, у вас есть массив как:

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

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

output = 0;

  • i = 4, j = 4;

если array1 [i] == array2 [j] возвращает false и ничего не делает.

output = 0;

  • i = 4, j = 3;

если array1 [i] == array2 [j] возвращает false и ничего не делает.

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.

затем проверьте, возвращает ли output <val [i] [j] истину, и действительно ли output = 1.

output = 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.

затем проверьте, возвращает ли output <val [i] [j] истину, и выполните output = val [i] [j].

output = 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.

затем проверьте, возвращает ли output <val [i] [j] истину, и выполните output = val [2] [0].

output = 3;

И это будет максимальная длина повторяющегося массива, равная 3, даже после того, как мы найдем элементы, равные при обходе, но он не будет выполнять обновление на выходе, потому что это не будет подмассив

скажем, при i = 1, j = 1 мы найдем следующий подобный элемент, чтобы он выполнил val [1] [1] = val [2] [2] +1;

и если мы проверим output <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

Анализ сложности для максимальной длины повторяющегося подмассива

Сложность времени

О (а × б) в котором «А» это размер первого массива и «Б» - размер второго массива.

Космическая сложность

О (а × б) в котором «А» это размер первого массива и «Б» - размер второго массива.

Справка