Задача: 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 {
    func longestArithSeqLength(_ nums: [Int]) -> Int {
        if nums.isEmpty { return 0 }
        
        var dp = Array(repeating: [Int: Int](), count: nums.count)
        var max_length = 0
        
        for i in 0..<nums.count {
            for j in 0..<i {
                let diff = nums[i] - nums[j]
                if let length = dp[j][diff] {
                    dp[i][diff] = length + 1
                } else {
                    dp[i][diff] = 2 // Start a new sequence
                }
                max_length = max(max_length, dp[i][diff]!)
            }
        }
        
        return max_length
    }
}

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