# 1027. Longest Arithmetic Subsequence
###### tags: `Leetcode` `Medium` `FaceBook` `Dynamic Programming` `Arithmetic Sequence`
Link: https://leetcode.com/problems/longest-arithmetic-subsequence/
## 思路 $O(N^2)$
dp[i] 代表截止到i位置，所有可能的等差数列的长度
dp的key是等差数列的差，value是当前等差数列的长度
**注意：第二个回圈不能反向遍历，也就是```for(int j=i-1; j>=0; j--)```，因为对于每一个diff，都要取当前长度的最大值**
## Code

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int res = 0;
        Map<Integer, Integer>[] dp = new HashMap[nums.length];
        for(int i = 0;i < nums.length;i++){
            dp[i] = new HashMap<>();
            for(int j = 0;j < i;j++){
                int diff = nums[i]-nums[j];
                dp[i].put(diff, dp[j].getOrDefault(diff,1)+1);
                res = Math.max(res, dp[i].get(diff));
            }
        }
        return res;
    }
}