最长等差数列

最长等差数列

给你一个整数数组 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 是等差的。

总结出一个问题:对于求子序列的问题,一般都可以使用动态规划的思想来做.如果子序列必须是连续的那么就很简单的可以找到转移方程和条件.如果子序列不要求是连续的,那么最常用的思路就是使用一个二维的动态规划数组,dp[n][m]其中n是序列的长度,m代表着所有可能的状态.
对于这道题,题目中所给数据是从 0 - 500 ，所以公差 d 的范围是 -500 ~ 500，为了表示方便，我们在计算时将公差加上500。

设置dp[n][1001]，dp[i][j] 表示以 nums[i] 结尾的公差为 j 的等差数列的最长值

public int longestArithSeqLength(int[] nums) {
        int len = nums.length;
        if(len<=2) return len;
        int[][] dp = new int[len][1001];
        int ans=0;

        for(int i=0;i<len;i++){
            for(int j=0;j<i;j++){
                //表示nums[i]与nums[j]以差为d构成等差数列
                int m = nums[i]-nums[j]+500;
                dp[i][m] = Math.max(dp[i][m], dp[j][m] + 1);
                ans = Math.max(ans,dp[i][m]);
            }
        }

        return ans+1;
    }
}