区间动态规划例题：最长等差数列的任意差值最大长度问题

题目描述

给你一个整数数组 nums，返回数组中最长等差数列（Arithmetic Progression, AP）的子数组的长度。等差数列是指任意相邻两项的差值相等的数列。请注意，本题要求的是连续的子数组，而不是子序列。

例如：

• 输入：nums = [3, 6, 9, 12]

• 输出：4

• 解释：整个数组本身就是公差为3的等差数列，所以最长长度为4。

• 输入：nums = [9, 4, 7, 2, 10]

• 输出：3

• 解释：最长的等差数列子数组是 [4, 7, 10]，公差为3，长度为3。

• 输入：nums = [1, 7, 10, 13, 14, 19]

• 输出：4

• 解释：最长的等差数列子数组是 [7, 10, 13, 16] 吗？不对，数组是 [1, 7, 10, 13, 14, 19]。实际上，[10, 13, 16] 不存在，正确的最长是 [1, 7, 13, 19] 吗？不，那不是连续的。连续的等差数列子数组是 [7, 10, 13] 公差为3，以及 [10, 13, 16] 不存在，[13, 16, 19] 不存在。实际上，数组中没有公差为3的连续四个数。仔细看，[1, 7, 13, 19] 是等差数列，但不是连续的（子数组要求连续元素）。在给定数组中，最长的连续等差数列是 [7, 10, 13] 长度为3，和 [10, 13, 16] 不存在，[13, 16, 19] 不存在，[1, 7, 13] 不连续。所以答案是3。但我们可以通过动态规划找到更长的，比如 [1, 4, 7, 10] 不存在。在 [9, 4, 7, 2, 10] 中，[4, 7, 10] 连续，公差3，长度为3。

实际上，我们想求的是任意公差下的最长连续等差数列的长度。这是LeetCode 413题"Arithmetic Slices"的扩展，但413题求的是算术切片（长度至少为3的连续等差子数组）的个数，而这里是求最长长度。

解题思路

本题可以使用动态规划解决，状态设计是关键。

1. 定义状态：
   设 dp[i] 表示以第 i 个元素结尾的、公差为某个值的等差数列的最大长度。但公差是未知的，所以我们用一个哈希表来记录以 nums[i] 结尾的、以不同公差为键的等差数列长度。
   更具体地，我们定义：

   dp[i][diff] = 以 nums[i] 结尾，且公差为 diff 的等差数列的最大长度
   

   但由于数组长度可能很大（比如1000），而公差可能非常多（每个差值都不同），我们可以在遍历时动态构建这个映射。

2. 状态转移：
   对于任意位置 i，我们考虑所有在它之前的元素 j（0 <= j < i），计算差值 diff = nums[i] - nums[j]。
   如果存在以 nums[j] 结尾、公差为 diff 的等差数列，那么我们可以将 nums[i] 接在这个等差数列后面，形成一个更长的等差数列，其长度是 dp[j][diff] + 1。
   如果不存在这样的等差数列，那么以 nums[i] 和 nums[j] 可以形成一个长度为2的等差数列（任何两个数都构成一个长度为2的等差数列）。
   所以我们有：

   length = dp[j].get(diff, 1) + 1
   dp[i][diff] = max(dp[i].get(diff, 2), length)
   

   这里 dp[j].get(diff, 1) 表示从 dp[j] 中获取公差为 diff 的长度，如果没有，则默认为1（即单独一个数的长度）。因为等差数列至少需要两个数，所以当我们把 nums[i] 接上去时，长度至少是 1+1=2。

3. 初始状态：
   每个位置 i 都可以单独成为一个长度为1的"数列"，但等差数列至少需要两个数，所以我们只需要考虑长度至少为2的情况。我们可以初始化一个字典列表，每个字典对应一个位置，记录以该位置结尾的不同公差的等差数列长度。

4. 记录最大值：
   在计算过程中，我们记录所有 dp[i][diff] 中的最大值，作为答案。

5. 复杂度：
   我们需要双层循环遍历 i 和 j，时间复杂度为 O(n^2)，空间复杂度为 O(n^2) 最坏情况（因为每个位置可能记录很多不同的公差）。

解题步骤详解

下面我们用一个具体例子 nums = [3, 6, 9, 12] 来逐步计算：

1. 初始化：

   n = len(nums) = 4
   创建一个长度为 n 的列表 dp，每个元素是一个字典（或哈希表）。
   dp[0] = {}  # 第一个数前面没有数，没有以它结尾的长度大于1的等差数列
   答案 ans 初始化为 1（至少一个数）
   

2. 遍历 i 从 1 到 n-1：

   • i = 1, nums[1] = 6

     • 遍历 j 从 0 到 0：
       • j = 0, nums[0] = 3, diff = 6 - 3 = 3
       • 查看 dp[0] 中是否有键 3，没有（dp[0] 为空），所以以 nums[1] 结尾、公差为3的等差数列长度是 2（即 [3,6]）。
       • 更新 dp[1][3] = 2
     • ans = max(ans, 2) = 2

   • i = 2, nums[2] = 9

     • 遍历 j 从 0 到 1：
       • j = 0, diff = 9 - 3 = 6
         • dp[0] 中没有键 6，所以 dp[2][6] = 2（数列 [3,9]）
       • j = 1, diff = 9 - 6 = 3
         • dp[1] 中有键 3，值为 2，所以我们可以接在后面：长度 = 2 + 1 = 3
         • 更新 dp[2][3] = 3（数列 [3,6,9]）
     • ans = max(ans, 3) = 3

   • i = 3, nums[3] = 12

     • 遍历 j 从 0 到 2：
       • j = 0, diff = 12 - 3 = 9
         • dp[0] 无键 9，所以 dp[3][9] = 2
       • j = 1, diff = 12 - 6 = 6
         • dp[1] 无键 6，所以 dp[3][6] = 2
       • j = 2, diff = 12 - 9 = 3
         • dp[2] 有键 3，值为 3，所以长度 = 3 + 1 = 4
         • 更新 dp[3][3] = 4（数列 [3,6,9,12]）
     • ans = max(ans, 4) = 4

3. 最终 ans = 4，即最长等差数列子数组长度为4。

代码实现（Python）

def longestArithmeticSubarray(nums):
    n = len(nums)
    if n <= 2:
        return n
    
    dp = [{} for _ in range(n)]
    ans = 2  # 至少两个数可以构成一个等差数列
    
    for i in range(1, n):
        for j in range(i):
            diff = nums[i] - nums[j]
            # 如果以 nums[j] 结尾存在公差为 diff 的等差数列，则长度+1，否则从2开始
            length = dp[j].get(diff, 1) + 1
            dp[i][diff] = max(dp[i].get(diff, 2), length)
            ans = max(ans, dp[i][diff])
    
    return ans

复杂度分析

• 时间复杂度：O(n^2)，因为有两层循环。
• 空间复杂度：O(n^2)，最坏情况下每个 dp[i] 可能存储 O(n) 个不同的公差，总共 O(n^2)。

边界情况

• 数组长度小于等于2时，直接返回数组长度，因为任意两个数都构成等差数列。
• 数组中可能有重复数字，此时公差为0，算法也能正确处理。
• 等差数列长度至少为2，如果数组所有数都相同，最长长度就是数组长度。

总结

本题通过动态规划，以每个位置为结尾，记录以不同公差形成的等差数列长度，逐步递推得到全局最长长度。关键在于状态设计为“以某个位置结尾、以某个公差为键的长度”，通过双层循环和哈希表实现高效查找和更新。