最长等差数列的长度（进阶版——允许公差为零且包含负数）

让我为您讲解这个线性动态规划问题。

问题描述

给定一个整数数组 nums，返回数组中最长等差数列的子序列长度。等差数列的公差可以是任意整数（包括0和负数），子序列不要求连续。

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

输入：nums = [9,4,7,2,10]
输出：3
解释：最长的等差数列是 [4,7,10]，公差为3

解题思路

第一步：理解问题本质

这是一个二维动态规划问题，我们需要记录以每个位置结尾、以特定公差结尾的最长等差数列长度。

第二步：状态定义

定义 dp[i][d] 表示以第 i 个元素结尾，公差为 d 的最长等差数列长度。

但由于公差 d 可能是任意整数，我们使用哈希表来存储：
dp[i] 是一个哈希表，键是公差 d，值是以 nums[i] 结尾、公差为 d 的最长等差数列长度。

第三步：状态转移方程

对于每个位置 i，我们遍历所有 j < i：

• 计算公差 d = nums[i] - nums[j]
• 如果 dp[j] 中存在公差 d，则 dp[i][d] = dp[j][d] + 1
• 否则 dp[i][d] = 2（至少包含 nums[j] 和 nums[i] 两个元素）

第四步：算法实现

def longestArithSeqLength(nums):
    n = len(nums)
    if n <= 2:
        return n
    
    # dp[i] 是一个字典，存储以nums[i]结尾，不同公差的最长序列长度
    dp = [dict() for _ in range(n)]
    max_length = 2  # 至少有两个元素
    
    for i in range(n):
        for j in range(i):
            diff = nums[i] - nums[j]
            
            # 如果j位置已经有这个公差的序列，就在其基础上加1
            if diff in dp[j]:
                dp[i][diff] = dp[j][diff] + 1
            else:
                # 否则，从j和i开始一个新的等差数列
                dp[i][diff] = 2
            
            max_length = max(max_length, dp[i][diff])
    
    return max_length

第五步：详细步骤分析

让我们用 nums = [3,6,9,12] 来逐步分析：

i=0: dp[0] = {} （第一个元素没有前驱）

i=1: 比较 nums[1]=6 与前面的元素

• j=0: diff = 6-3 = 3
• dp[1][3] = 2

i=2: 比较 nums[2]=9 与前面的元素

• j=0: diff = 9-3 = 6, dp[2][6] = 2
• j=1: diff = 9-6 = 3, dp[2][3] = dp[1][3] + 1 = 3

i=3: 比较 nums[3]=12 与前面的元素

• j=0: diff = 12-3 = 9, dp[3][9] = 2
• j=1: diff = 12-6 = 6, dp[3][6] = dp[2][6] + 1 = 3
• j=2: diff = 12-9 = 3, dp[3][3] = dp[2][3] + 1 = 4

最终得到最长等差数列长度为4。

第六步：复杂度分析

• 时间复杂度：O(n²)，需要两层循环遍历所有元素对
• 空间复杂度：O(n²)，最坏情况下每个位置可能存储O(n)个不同的公差

第七步：优化考虑

虽然理论上最坏情况空间复杂度是O(n²)，但在实际应用中，由于整数范围通常有限，实际使用的空间会小很多。

这个解法能够正确处理：

• 公差为0的情况（所有相同元素）
• 公差为负数的情况
• 不连续的子序列
• 重复元素的情况

这个问题的关键在于理解等差数列的性质，以及如何通过动态规划来记录不同公差下的序列长度。