Сложность: medium
Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.
Пример:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
👨💻 Алгоритм:
1⃣Создайте двумерный массив для хранения длин общих подмассивов.
2⃣Используйте динамическое программирование для нахождения максимальной длины общего подмассива.
3⃣Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива.
😎 Решение:
def findLength(nums1, nums2):
dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
max_len = 0
for i in range(len(nums1) - 1, -1, -1):
for j in range(len(nums2) - 1, -1, -1):
if nums1[i] == nums2[j]:
dp[i][j] = dp[i + 1][j + 1] + 1
max_len = max(max_len, dp[i][j])
return max_len
Ставь 👍 и забирай 📚 Базу знаний