区间动态规划例题：最长等差数列问题（不同约束版本）

题目描述

给定一个整数数组 nums，返回数组中最长等差数列的子序列长度。等差数列是指至少包含三个元素的序列，且任意相邻两个元素的差相等。注意：子序列不要求连续，但必须保持原始顺序。

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

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

解题过程

1. 问题分析

   • 我们需要找到最长的等差数列子序列
   • 等差数列由两个关键要素决定：最后一个元素和公差
   • 子序列不要求连续，这增加了问题的复杂性

2. 动态规划状态定义

   • 定义 dp[i][d] 表示以第 i 个元素结尾，公差为 d 的等差数列长度
   • 但是公差 d 可能是任意整数，范围可能很大，这种定义方式不够高效

3. 优化状态定义

   • 使用二维数组 dp[i][j] 表示以 nums[i] 和 nums[j] 作为最后两个元素的等差数列长度
   • 其中 0 ≤ i < j < n
   • 对于这样的等差数列，公差 d = nums[j] - nums[i]

4. 状态转移方程

   • 对于每个位置对 (i, j)，我们需要找到前一个元素的位置 k
   • 使得 nums[k] + d = nums[i]，即 nums[k] = 2 × nums[i] - nums[j]
   • 如果存在这样的 k（0 ≤ k < i），那么：
     dp[i][j] = dp[k][i] + 1
   • 否则，最小长度为2（任意两个数都构成长度为2的等差数列）

5. 算法步骤

   def longestArithSeqLength(nums):
       n = len(nums)
       if n <= 2:
           return n
   
       # 创建dp数组，初始化为2
       dp = [[2] * n for _ in range(n)]
       max_len = 2
   
       # 创建索引映射，快速查找特定值的位置
       index_map = {}
       for i in range(n):
           index_map[nums[i]] = i
   
       # 遍历所有可能的(i,j)对
       for i in range(n):
           for j in range(i + 1, n):
               # 计算前一个元素应该的值
               prev = 2 * nums[i] - nums[j]
   
               # 检查前一个元素是否存在且在i之前
               if prev in index_map and index_map[prev] < i:
                   k = index_map[prev]
                   dp[i][j] = dp[k][i] + 1
                   max_len = max(max_len, dp[i][j])
   
       return max_len
   

6. 复杂度分析

   • 时间复杂度：O(n²)，需要遍历所有(i,j)对
   • 空间复杂度：O(n²)，用于存储dp数组

7. 边界情况处理

   • 数组长度小于3时直接返回数组长度
   • 处理所有元素都相同的情况（公差为0）
   • 处理严格递增或递减的情况

关键理解点

• 通过记录最后两个元素来隐含记录公差信息
• 使用哈希表快速查找前一个元素的位置
• 任意两个元素默认构成长度为2的"等差数列"
• 只有当找到第三个满足条件的元素时，才能形成真正的等差数列