Задача: 718. Maximum Length of Repeated Subarray
Если даны два целочисленных массива 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;
}👉Новости 👉База вопросов
