本文共 2176 字，大约阅读时间需要 7 分钟。

1. 题目

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

回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。

示例 1：输入：[3,6,9,12]输出：4解释： 整个数组是公差为 3 的等差数列。示例 2：输入：[9,4,7,2,10]输出：3解释：最长的等差子序列是 [4,7,10]。示例 3：输入：[20,1,15,3,10,5,8]输出：4解释：最长的等差子序列是 [20,15,10,5]。 提示：2 <= A.length <= 20000 <= A[i] <= 10000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-arithmetic-sequence

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

• dp[idx][diff]， 表示以 idx 结尾，差为 diff 的最长等差数组长度
• 类似于最长上升子序

class Solution {
   public:    int longestArithSeqLength(vector
   
    & A) {
       	int i, j, d, n = A.size(), maxlen = 2;    	unordered_map
    
     
      > m;//idx，差，最大长度    	for(i = 0; i < n; i++)     	{
       		for(j = i-1; j >= 0; --j)    		{
       			d = A[i]-A[j];    			if(m[j][d])    				m[i][d] = max(m[i][d], m[j][d] + 1);    			else    				m[i][d] = max(m[i][d], 2);    			maxlen = max(maxlen, m[i][d]);    		}    	}    	return maxlen;    }};
     
    
   

5236 ms 388.1 MB

• 优化，用数组加速

class Solution {
   public:    int longestArithSeqLength(vector
   
    & A) {
       	int i, j, d, n = A.size(), maxlen = 2;    	vector
    
     
      > m(n,vector
      
       (20001,0));//m[idx][差]，最大长度    	for(i = 0; i < n; i++)     	{
       		for(j = i-1; j >= 0; --j)    		{
       			d = A[i]-A[j];    			if(d < 0)    				d = -d + 10000;    			if(m[j][d])    				m[i][d] = max(m[i][d], m[j][d] + 1);    			else    				m[i][d] = max(m[i][d], 2);    			maxlen = max(maxlen, m[i][d]);    		}    	}    	return maxlen;    }};
      
     
    
   

408 ms 474 MB

• python3 解答

class Solution:# py3    def longestArithSeqLength(self, A: List[int]) -> int:        n = len(A)        maxlen = 2        m = [[0]*20001 for _ in range(n)] # m[idx][差]，最大长度        for i in range(1,n):            for j in range(0,i):                d = A[i]-A[j];                if d < 0:                    d = -d + 10000;                if m[j][d]:                    m[i][d] = max(m[i][d], m[j][d] + 1)                else:                    m[i][d] = max(m[i][d], 2)                maxlen = max(maxlen, m[i][d])        return maxlen

2248 ms 326.2 MB

转载地址：https://michael.blog.csdn.net/article/details/106820302 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！