1027. Longest Arithmetic Sequence

https://leetcode.com/problems/longest-arithmetic-sequence/

找数组中最长等差序列的长度。longes + subseq => DP。和LIS类似每步看当前元素i作为最长等差seq尾时能有多长等，action为选前面的元素j拼接在后面，受限于i与j的diff和以该diff且尾为j的等差有多长。因此DP[i][diff]表以i为底部且等差距离为diff的最长subseq长度。

/*
 * @lc app=leetcode id=1027 lang=cpp
 *
 * [1027] Longest Arithmetic Sequence
 */

// @lc code=start
class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        const int N = A.size();
        vector<unordered_map<int, int>> dp(N);
        int res = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < i; ++j) {
                const auto diff = A[i] - A[j];
                if (dp[j].count(diff)) {
                    dp[i][diff] = dp[j][diff] + 1;
                } else {
                    dp[i][diff] = 2;
                }
                res = max(res, dp[i][diff]);
            }
        } 
        return res;
    }
};
// @lc code=end