区间动态规划例题：最长等差数列问题（任意差值版本） 题目描述 给定一个整数数组 nums ，返回该数组中最长等差数列的子序列长度。等差数列的定义是：至少包含三个元素，且任意两个相邻元素的差相等。数组中的元素顺序不能改变，但可以不连续。例如，对于输入 [3,6,9,12] ，最长等差数列是 [3,6,9,12] ，长度为 4；对于 [9,4,7,2,10] ，最长等差数列是 [4,7,10] ，长度为 3。 解题思路 问题分析 ：本题要求找出最长的等差数列子序列（允许不连续），关键在于确定公差（差值）不固定，需要动态记录以每个元素结尾、不同公差下的最长等差数列长度。 状态定义 ：使用 dp[i][d] 表示以第 i 个元素结尾、公差为 d 的等差数列的最大长度。但公差可能很大，直接使用二维数组会内存溢出，因此改用哈希表嵌套字典（或类似结构）来存储。 状态转移 ：对于每个位置 i ，遍历其之前的所有位置 j （ j < i ），计算差值 d = nums[i] - nums[j] 。若存在以 j 结尾、公差为 d 的等差数列，则 dp[i][d] = dp[j][d] + 1 ；否则初始化为 2（因为两个元素可构成等差数列的雏形）。 结果提取 ：遍历所有 i 和 d ，记录最大值。若结果小于 3，按题意返回 0（因等差数列需至少 3 个元素）。 逐步详解 初始化 ： 创建字典 dp ，其中 dp[i] 是一个字典，键为公差 d ，值为以 i 结尾、公差为 d 的等差数列长度。 初始化最长长度 max_len = 2 （最小可能值）。 遍历数组 ： 外层循环 i 从 0 到 n-1 ，内层循环 j 从 0 到 i-1 。 计算 d = nums[i] - nums[j] 。 若 dp[j] 中存在键 d ，则 dp[i][d] = dp[j][d] + 1 ；否则 dp[i][d] = 2 。 更新 max_len = max(max_len, dp[i][d]) 。 边界处理 ： 若数组长度小于 3，直接返回 0。 最终若 max_len < 3 则返回 0，否则返回 max_len 。 举例说明 以 nums = [9,4,7,2,10] 为例： i=1 （元素4）：与 j=0 （元素9）比较， d=4-9=-5 ， dp[1][-5]=2 。 i=2 （元素7）： 与 j=0 （9）比较， d=7-9=-2 ， dp[2][-2]=2 。 与 j=1 （4）比较， d=7-4=3 ， dp[2][3]=2 。 i=3 （元素2）： 与 j=1 （4）比较， d=2-4=-2 ，此时 dp[1] 无 -2 ，故 dp[3][-2]=2 。 与 j=2 （7）比较， d=2-7=-5 ， dp[2] 无 -5 ，故 dp[3][-5]=2 。 i=4 （元素10）： 与 j=2 （7）比较， d=10-7=3 ， dp[2][3]=2 ，故 dp[4][3]=3 （序列 [4,7,10] ）。 更新 max_len=3 。 最终结果为 3。 复杂度分析 时间复杂度：O(n²)，需要两重循环遍历所有元素对。 空间复杂度：O(n²)，最坏情况下每个 i 可能存储 O(n) 个不同的公差。