Сложность: 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 после завершения итерации.
😎 Решение:
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
unordered_map<int, int> dp;
int answer = 1;
for (int a : arr) {
int beforeA = dp.count(a - difference) ? dp[a - difference] : 0;
dp[a] = beforeA + 1;
answer = max(answer, dp[a]);
}
return answer;
}
};Ставь 👍 и забирай 📚 Базу знаний