Задача: 718. Maximum Length of Repeated Subarray
Сложность: medium

Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.

Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

👨‍💻 Алгоритм:

1⃣Создайте двумерный массив для хранения длин общих подмассивов.

2⃣Используйте динамическое программирование для нахождения максимальной длины общего подмассива.

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

😎 Решение:

function findLength($nums1, $nums2) {
    $dp = array_fill(0, count($nums1) + 1, array_fill(0, count($nums2) + 1, 0));
    $maxLength = 0;
    for ($i = count($nums1) - 1; $i >= 0; $i--) {
        for ($j = count($nums2) - 1; $j >= 0; $j--) {
            if ($nums1[$i] == $nums2[$j]) {
                $dp[$i][$j] = $dp[$i + 1][$j + 1] + 1;
                $maxLength = max($maxLength, $dp[$i][$j]);
            }
        }
    }
    return $maxLength;
}

Ставь 👍 и забирай 📚 Базу знаний