区间动态规划例题：最长等差数列问题（不同约束版本） 题目描述 给定一个整数数组 nums ，返回数组中最长等差数列的子序列长度。注意：子序列不要求连续，但必须保持原始顺序。例如，对于 nums = [3,6,9,12] ，最长等差数列是 [3,6,9,12] ，长度为 4。 解题过程 问题分析 与连续子数组不同，子序列允许跳过元素。我们需要找到最长的等差子序列。等差由公差 d 决定，但 d 可能为正、负或零，且不确定。直接枚举所有可能的子序列和公差会超时。 动态规划状态定义 设 dp[i][d] 表示以第 i 个元素结尾、公差为 d 的最长等差数列长度。但 d 的范围可能很大（如 -10^4 到 10^4 ），需用哈希表优化。 更优方案：定义 dp[i][j] 表示以 nums[i] 和 nums[j] 作为最后两项的等差数列长度（ i < j ）。公差 d = nums[j] - nums[i] 。 状态转移：对于任意 k < i ，若 nums[i] - nums[k] = nums[j] - nums[i] ，则 dp[i][j] = dp[k][i] + 1 。 状态转移方程 基础情况：任意两点 (i, j) 至少构成长度为 2 的等差序列，故初始化 dp[i][j] = 2 。 转移：遍历所有 k （ 0 ≤ k < i ），若 nums[i] - nums[k] = nums[j] - nums[i] ，则更新： \[ dp[ i][ j] = \max(dp[ i][ j], dp[ k][ i ] + 1) \] 最终答案：所有 dp[i][j] 的最大值。 实例演示 以 nums = [3,6,9,12] 为例： 初始化 dp[i][j] = 2 。 对于 (i,j)=(1,2) ：公差 d=3 ，找 k=0 满足 nums[1]-nums[0]=3=d ，则 dp[1][2] = dp[0][1] + 1 = 3 。 对于 (i,j)=(2,3) ：公差 d=3 ，找 k=1 满足条件，则 dp[2][3] = dp[1][2] + 1 = 4 。 最大值为 4。 复杂度优化 直接三重循环会超时（O(n³)）。优化：用哈希表记录每个值的最新索引，遍历时直接查找满足条件的 nums[k] = 2*nums[i] - nums[j] 的索引 k ，降至 O(n²)。 边界情况 数组长度 ≤ 2 时，直接返回长度。 公差可能为负数，但计算时直接相减即可处理。 总结 本题通过固定等差数列最后两项，将问题转化为寻找中间点 k 的匹配问题，利用动态规划记录状态，并通过哈希表优化查找，最终在 O(n²) 时间内求解。