您现在的位置是：首页 >技术教程 >1027. 最长等差数列网站首页技术教程

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

示例 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]。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-arithmetic-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
题意很好理解，就是给出一组数，让你找到最长的等差数列。

这道题如何开始思考呢？

首先从手推的角度来考虑的话，就是从第一个数开始，先后开始检查每个数字。每到一个数字的时候，你就要看，这个数字和之前的每个数字是否能够成等差数列，能的话就将当前数字加入进去，长度加一，当前数字作为结尾。

好的，思考到这里，是不是想法已经很明确了？

每个数字都可以从前面的数字的一个状态转移而来，这不就是DP问题嘛！

ok,直接一个状态转移方程给他拿下。

首先是定义状态表示，dp【i】【j】的含义是以第 i 个数字结尾的，j 为差值的序列最大长度。

首先一个初始化，因为每一个数字都可以单独作为一个等差数列，因此，初始化dp[i][j]为1。这里 i 是0到 n ，因为一共有 n 个数字。j 的范围是0到1001。因为本题中数字的范围是0到500，所以等差数列的差值范围是-500到+500，那数组下标我们知道是不能取负值的，因此我们将dp数组的第二维都向右平移500，这样第二维的范围就从 -500~500 变成了 0到1000 ，也就是 j 的范围。

OK，初始化完毕后，就要开始我们的状态转移方程了。刚才我们介绍过思路，i 从 0到n ， j 从 0 到 i-1 ，dp[i][nums[i]-nums[j]+c]表示以第 i 个数为结尾，差值为nums[i]-nums[j]的序列长度。+c的含义解释过，是为了避免出现负值。

那状态转移方程就是：
dp[i][nums[i]-nums[j]+c] = max(dp[i][nums[i]-nums[j]+c] , dp[j][nums[i]-nums[j]+c]+1)

如果当前数能满足和nums[j]构成等差数列，那就是当前nums[i]结尾和nums[j]结尾+1两者取最大值。
如果不满足，那就是当前nums[i]结尾的值。

因为要的是最长的子序列长度的值，那其实是不一定以哪个位置作为序列末尾的，所以我们需要遍历一遍所有的dp元素，找到最大值。

代码：

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        int c = 500;
        int dp[n][1001];
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < 1001 ; j++)
                dp[i][j] = 1;
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < i ; j++)
                dp[i][nums[i]-nums[j]+c] = max(dp[i][nums[i]-nums[j]+c] , dp[j][nums[i]-nums[j]+c]+1);
        int res = 1;
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < 1001 ; j++)
                res = max(res , dp[i][j]);
        return res;
    }
};