1.题目

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i₁], nums[i₂], …, nums[i_k] ，且 0 <= i₁ < i₂ < … < i_k <= nums.length - 1。并且如果 seq[i + 1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：
输入：nums = [3,6,9,12]
输出：4
解释：
整个数组是公差为 3 的等差数列。

示例 2：
输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

示例 3：
输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

提示：
2 <= nums.length <= 1000
0 <= nums[i] <= 500

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-arithmetic-subsequence

2.思路

（1）动态规划
思路参考本题官方题解。

① 设 minNum 和 maxNum 分别为数组 nums 中的最大值和最小值，那么子序列的公差 d 的取值范围为 [minNum - maxNum, maxNum - minNum]；

② 枚举所有可能的公差 d，在每次枚举的过程中定义以下 dp 数组并进行初始化，dp[i] 表示以 nums[i] 结尾且公差为 d 的最长子序列长度。

 int[] dp = new int[maxNum + 1];
 //因为以 nums[i] 结尾且公差为 d 的最长子序列不一定存在，因此先将其值初始化为 -1，方便后续进行判断
 Arrays.fill(dp, -1);

③ 对于每一个 d，遍历数组 nums 中的每一个元素 num：

• 如果 prev = num - d 未超出数组值范围的边界，并且 dp[prev] != -1，则说明以 nums[prev] 结尾且公差为 d 的最长子序列存在，此时则需要更新 dp[num] 与 res：

dp[num] = Math.max(dp[num], dp[prev] + 1);
res = Math.max(res, dp[num]);

• 否则，将 dp[num] 更新为 Math.max(dp[num], 1)

④ 枚举完 d 后，直接返回 res 即可。

3.代码实现（Java）

//思路1————
class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int minNum = Arrays.stream(nums).min().getAsInt();
        int maxNum = Arrays.stream(nums).max().getAsInt();
        int diff = maxNum - minNum;
        int res = 2;
        //枚举所有可能的公差
        for (int d = -diff; d <= diff; d++) {
            // dp[i] 表示以 nums[i] 结尾且公差为 d 的最长子序列长度
            int[] dp = new int[maxNum + 1];
            //因为以 nums[i] 结尾且公差为 d 的最长子序列不一定存在，因此先将其值初始化为 -1，方便后续进行判断
            Arrays.fill(dp, -1);
            for (int num : nums) {
                int prev = num - d;
                /*
                    prev >= minNum && prev <= maxNum: 判断边界
                    dp[prev] != -1 说明以 nums[prev] 结尾且公差为 d 的最长子序列存在
                */
                if (prev >= minNum && prev <= maxNum && dp[prev] != -1) {
                    //更新 dp[num] 与 res
                    dp[num] = Math.max(dp[num], dp[prev] + 1);
                    res = Math.max(res, dp[num]);
                }
                dp[num] = Math.max(dp[num], 1);
            }
        }
        return res;
    }
}