Сложность: medium
Дан массив целых чисел arr и целое число difference. Верните длину самой длинной подпоследовательности в arr, которая является арифметической последовательностью, так что разница между соседними элементами в подпоследовательности равна difference.
Подпоследовательность — это последовательность, которую можно получить из arr, удалив некоторые или ни одного элемента, не меняя порядок оставшихся элементов.
Пример:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].
👨💻 Алгоритм:
1⃣Инициализируйте пустой хеш-таблицу dp и установите answer = 1.
2⃣Итеративно обработайте массив arr. Для каждого элемента arr[i]:
Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference:
- если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference].
- в противном случае, установите before_a = 0.
Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]).
3⃣Верните answer после завершения итерации.
😎 Решение:
var longestSubsequence = function(arr, difference) {
let dp = new Map();
let answer = 1;
for (let a of arr) {
let beforeA = dp.get(a - difference) || 0;
dp.set(a, beforeA + 1);
answer = Math.max(answer, dp.get(a));
}
return answer;
};Ставь 👍 и забирай 📚 Базу знаний