Сложность: 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(int[] arr, int difference) {
Map<Integer, Integer> dp = new HashMap<>();
int answer = 1;
for (int a : arr) {
int beforeA = dp.getOrDefault(a - difference, 0);
dp.put(a, beforeA + 1);
answer = Math.max(answer, dp.get(a));
}
return answer;
}
}Ставь 👍 и забирай 📚 Базу знаний