Задача: 1218. Longest Arithmetic Subsequence of Given Difference
Сложность: 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 после завершения итерации.

😎 Решение:

public class Solution {
    public int LongestSubsequence(int[] arr, int difference) {
        Dictionary<int, int> dp = new Dictionary<int, int>();
        int answer = 1;
        
        foreach (int a in arr) {
            int beforeA = dp.ContainsKey(a - difference) ? dp[a - difference] : 0;
            dp[a] = beforeA + 1;
            answer = Math.Max(answer, dp[a]);
        }
        
        return answer;
    }
}

Ставь 👍 и забирай 📚 Базу знаний