Python | LeetCode
Задача: 1027. Longest Arithmetic Subsequence
Сложность: medium
Если задан массив nums целых чисел, верните длину самой длинной арифметической подпоследовательности в nums. Примечание: Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1).
Пример:
Input: nums = [3,6,9,12]
Output: 4
👨💻 Алгоритм:
1⃣Инициализация переменных:
Создайте массив словарей dp, где dp[i][d] будет хранить длину самой длинной арифметической подпоследовательности, заканчивающейся на элементе i с разностью d.
2⃣Заполнение массива dp:
Пройдитесь по каждому элементу массива nums.
Для каждого элемента nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j].
Обновите dp[i][d] на основе значения dp[j][d].
3⃣Поиск максимальной длины:
Пройдите по массиву dp и найдите максимальное значение среди всех значений dp[i][d].
😎 Решение:
class Solution:
def longestArithSeqLength(self, nums: List[int]) -> int:
if not nums:
return 0
dp = [{} for _ in range(len(nums))]
max_length = 0
for i in range(len(nums)):
for j in range(i):
diff = nums[i] - nums[j]
if diff in dp[j]:
dp[i][diff] = dp[j][diff] + 1
else:
dp[i][diff] = 2 # Start a new sequence
max_length = max(max_length, dp[i][diff])
return max_length
Ставь 👍 и забирай 📚 Базу знаний
5 · 658 ·