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

回想一下，nums的子序列是一个列表nums[i1], nums[i2],..., nums[ik]，且0<= i1 < i2 <…… < ik <= nums.length -1

 ，并且如果seq[i+1] - seq[i]( 0 <= i < seq.length-1）的值都相同，那么seq序列是等差的。

1027. 最长等差数列 - 力扣（Leetcode）

示例一：

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

示例二：

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

实例三：

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

提示：

• 2 <= nums.length <= 1000

• 0 <= nums[i] <= 500

分析：动态数组

我们定义dp[ i ] [ j ]表示以num[ i ] 结尾的且公差为 j 的等差数列的最大长度。初始时 dp[ i ][ j ] = 1，表示每一个元素都是公差为1的等差数列

由于公差可能为负数，且最大差值为 500500500，因此，我们可以将统一将公差加上 500500500，这样公差的范围就变成了 [0,1000][0, 1000][0,1000]。

考虑 f[i]f[i]f[i]，我们可以枚举 nums[i] 的前一个元素 nums[k]，那么公差 j=nums[i]−nums[k]+500，此时有 f[i][j]= max⁡(f[i][j],f[k][j]+1)，然后我们更新答案ans = max(ans, f[i][j])。

最后返回答案即可：

如果初始时f[i][j]=0，那么我们需要在最后返回答案时加上 1。

代码

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int[][] f = new int[n][1001];
        for (int i = 1; i < n; ++i) {
            for (int k = 0; k < i; ++k) {
                int j = nums[i] - nums[k] + 500;
                f[i][j] = Math.max(f[i][j], f[k][j] + 1);
                ans = Math.max(ans, f[i][j]);
            }
        }
        return ans + 1;
    }
}