区间动态规划例题：最长等差数列问题（通用差值版本） 题目描述 给定一个整数数组 nums ，返回该数组中最长等差数列的子序列长度。等差数列的定义是：至少包含三个元素，且任意相邻两个元素的差值相等。差值可以是正数、负数或零。例如，对于数组 [3, 6, 9, 12] ，其差值为 3，是等差数列；数组 [9, 4, -1, -6] 的差值为 -5，也是等差数列。注意：子序列不要求连续，但顺序必须与原数组一致。 示例 输入： nums = [9, 4, 7, 2, 10] 输出：3 解释：最长的等差数列是 [4, 7, 10] ，差值为 3。 解题过程 1. 问题分析 目标：在数组中找到一个最长的子序列，使其成为等差数列。 难点：差值不确定，且子序列不要求连续。暴力枚举所有子序列不可行。 关键思路：使用动态规划记录以特定位置结尾、具有特定差值的等差数列长度。 2. 状态定义 定义 dp[i][d] 表示以第 i 个元素结尾、差值为 d 的等差数列的最大长度。 由于差值 d 可能是任意整数，直接使用二维数组会过大。优化：用哈希表存储差值。 实际实现中，常使用 dp[i] 是一个字典（或映射），键为差值 d ，值为长度。 3. 状态转移方程 对于每个位置 i ，遍历其之前的所有位置 j （0 ≤ j < i）： 计算差值 d = nums[i] - nums[j] 。 如果 dp[j] 中存在键 d ，说明存在以 j 结尾、差值为 d 的等差数列，则延长该数列： dp[i][d] = dp[j][d] + 1 。 如果 dp[j] 中不存在键 d ，说明从 j 到 i 可形成长度为 2 的等差数列（初始状态）： dp[i][d] = 2 。 注意：长度为 2 的数列本身不构成等差数列（题目要求至少三个元素），但它是潜在等差数列的起点。 4. 初始化 每个位置 i 至少可以单独作为一个元素，但等差数列至少需要两个元素才能定义差值。 初始化每个 dp[i] 为空字典，在遍历过程中填充。 5. 计算步骤（以示例 nums = [ 9, 4, 7, 2, 10] 为例） i = 0 ：无前驱元素， dp[0] 为空。 i = 1 ：比较 j=0，差值 d=4-9=-5， dp[1][-5] = 2 。 i = 2 ： j=0：d=7-9=-2， dp[2][-2] = 2 。 j=1：d=7-4=3， dp[2][3] = 2 。 i = 3 ： j=0：d=2-9=-7， dp[3][-7] = 2 。 j=1：d=2-4=-2，检查 dp[2] 中是否有 d=-2？有（值为2），则 dp[3][-2] = dp[2][-2] + 1 = 3 （数列 [ 9, 7, 2 ]）。 j=2：d=2-7=-5， dp[3][-5] = 2 （因为 dp[1] 有 d=-5，但值为2，直接继承会重复？不，这里应取 dp[1][-5] + 1 = 3 ？注意：数列是 [ 4, 2] 差值为 -2？纠正：d=2-7=-5，而 dp[1] 的键 -5 对应数列 [ 9,4]？不，j=2 时，应看 dp[j]=dp[2] 中是否有 d=-5？没有，所以设 dp[3][-5]=2 ）。 i = 4 ： j=0：d=10-9=1， dp[4][1]=2 。 j=1：d=10-4=6， dp[4][6]=2 。 j=2：d=10-7=3，检查 dp[2] 有 d=3（值为2），则 dp[4][3] = 3 （数列 [ 4,7,10 ]）。 j=3：d=10-2=8， dp[4][8]=2 。 6. 记录最大值 在填充 dp[i][d] 时，持续跟踪最大值。注意：只有长度 ≥3 时才更新答案（但初始长度为2的数列在后续可能被延长为3）。最终最大值为3。 7. 复杂度优化 时间复杂度：O(n²)，因需双重循环。 空间复杂度：使用 O(n²) 的哈希表存储（最坏情况每个 i 有 O(n) 个差值）。 8. 边界情况 数组长度小于3时，直接返回0（无等差数列）。 差值可能很大，但哈希表可灵活处理。 通过以上步骤，即可高效求出最长等差数列的长度。