区间动态规划例题：最长等差数列问题（任意差值版本） 题目描述 给定一个整数数组 nums ，返回数组中最长等差数列的子序列长度。等差数列的定义是：一个序列中任意相邻两项的差相等，这个差值可以是任意整数（包括0和负数）。例如，对于数组 [3,6,9,12,7,10,8] ，最长等差数列是 [3,6,9,12] ，长度为4。注意：子序列不要求连续，但必须保持原始顺序。 解题过程 步骤1：理解问题与定义状态 我们需要找到最长的等差数列子序列。由于差值可以是任意整数，且子序列不连续，直接枚举所有可能的差值会非常低效。考虑使用动态规划，定义状态： dp[i][d] 表示以索引 i 结尾、公差为 d 的最长等差数列长度。 但公差 d 的范围可能很大（例如差值从 -500 到 500），直接使用二维数组可能内存过大。我们可以用哈希表来存储公差。 改进状态定义 ： dp[i] 是一个哈希表，键是公差 d ，值是以 nums[i] 结尾、公差为 d 的等差数列长度。 步骤2：状态转移方程 对于每个位置 i ，我们检查所有前面的位置 j （0 ≤ j < i），计算差值 d = nums[i] - nums[j] 。 如果 j 的哈希表中存在键 d ，说明存在以 nums[j] 结尾、公差为 d 的等差数列，我们可以将 nums[i] 接在这个数列后面，长度加1： dp[i][d] = dp[j][d] + 1 如果 j 的哈希表中没有键 d ，说明从 j 到 i 可以形成一个长度为2的等差数列： dp[i][d] = 2 步骤3：初始化 每个单独的元素可以视为长度为1的等差数列（任何公差都成立，但实际我们只关心长度≥2的情况）。初始化时，每个 dp[i] 是一个空哈希表，默认情况下任何位置自身形成的数列长度为1。 步骤4：计算顺序与记录最大值 按从左到右的顺序遍历 i ，对于每个 i ，遍历所有 j < i ，更新 dp[i][d] 。同时用一个变量 maxLen 记录全局最大长度。 步骤5：示例演算 以 nums = [3,6,9,12,7,10,8] 为例： i=0: dp[ 0 ] = {} i=1: j=0, d=3 → dp[ 1][ 3 ] = 2 i=2: j=0, d=6 → dp[ 2][ 6 ] = 2 j=1, d=3 → dp[ 2][ 3] = dp[ 1][ 3 ] + 1 = 3 i=3: j=0, d=9 → dp[ 3][ 9 ] = 2 j=1, d=6 → dp[ 3][ 6 ] = 2 j=2, d=3 → dp[ 3][ 3] = dp[ 2][ 3 ] + 1 = 4 此时 maxLen = 4 继续处理剩余元素... 步骤6：复杂度优化 使用哈希表存储公差，最坏情况下每个 dp[i] 可能有 O(n) 个键，总复杂度 O(n²)，空间 O(n²)。对于较大n可能超内存，但题目一般n≤1000时可接受。 步骤7：边界情况 数组长度≤2时，直接返回数组长度。 所有元素相同的情况，公差为0，最长等差数列长度就是数组长度。 步骤8：实现要点 使用字典列表或哈希表数组来存储 dp ，遍历时更新并跟踪最大值。 通过以上步骤，我们可以高效求出任意差值的最长等差数列子序列长度。这个方法的关键是利用哈希表灵活存储不同公差对应的序列长度，避免枚举所有可能差值。