Задача: 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 {
public:
    int longestArithSeqLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int n = nums.size();
        vector<unordered_map<int, int>> dp(n);
        int max_length = 0;
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int diff = nums[i] - nums[j];
                if (dp[j].count(diff)) {
                    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;
    }
};

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