题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个整数数组 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 <= 2000
0 <= A[i] <= 10000

解答

对于数组问题，如果寻找连续子数组，可以使用双指针法或滑动窗口等方法，但是对于非连续子数组，最好使用动态规划。

【数组定义】
这道题特殊的是，我们不仅需要知道当前的遍历信息，也就是两个数字之间的差值，还需要知道历史信息，也就是曾经遍历时是否出现过差值一样的情况。对于需要知道历史信息的遍历过程，我们使用哈希表作为暂存器，达到快速检索的功能。

定义字典dp，字典的键是一个元组，里面包含两个元素，第一个是元素下标index，第二个是以index处元素结尾的等差数列的步长step，字典的值是该等差数列的长度。举个例子，对于数组[1,2,3,5,9,11,12,15]，字典{(6, 3):3}表达的含义就是以A[6]=15结尾，步长为3的等差数列的长度为3，也就是[9,12,15]。

【初始状态】
将字典dp设置为空即可，我们要在里面添加元素。

【递推公式】
dp的填充需要两重嵌套，成对的研究数组中两个位置previous，end,previous<end，它们的差值step = A[end] - A[previous]，我们就要看了，(previous, step)是否已经出现在dp中，如果是，则说明，end位置所在元素可以接在以previous结尾，以step为步长的等差数组中，则dp数组中添加状态dp[(end, step)]=dp[(previous, step)]+1，加一意思是加入了end位置处的元素，否则，说明end和previous确定了一个新的只含有两个元素的等差数组，dp[(end, step)]=2，两种情况合二为一，就是dp[(end, step)] = dp.get((previous, step), 1) + 1。

遍历过程中，需要及时的更新最终结果max_ans = max(max_ans, dp[(end, step)])，或者在最后给出max(dp.values())。

class Solution:
    def longestArithSeqLength(self, A) -> int:
        dp = dict()
        for end in range(1, len(A)):
            for previous in range(end):
                step = A[end] - A[previous]
                dp[(end, step)] = dp.get((previous, step), 1) + 1
        return max(dp.values())

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析