线性动态规划：最长等差数列的长度（进阶版——允许公差为负） 题目描述 给定一个整数数组 nums ，返回该数组中最长等差数列的长度。等差数列的公差可以是正数、负数或零。例如，对于数组 [3, 6, 9, 12] ，最长等差数列是 [3, 6, 9, 12] ，长度为 4；对于数组 [9, 4, 7, 2, 10] ，最长等差数列是 [4, 7, 10] ，长度为 3。 解题过程 问题分析 目标：找到最长的子序列（不要求连续），使其构成等差数列。 难点：公差可为负，且子序列不要求连续，需动态规划记录状态。 动态规划状态定义 定义 dp[i][d] 表示以 nums[i] 结尾、公差为 d 的最长等差数列的长度。 但公差 d 可能很大，直接作为数组下标不现实。优化方案：使用哈希表存储公差。 实际定义： dp[i] 是一个字典（哈希表），键为公差 d ，值为以 nums[i] 结尾、公差为 d 的等差数列长度。 状态转移方程 遍历每一对 (j, i) （其中 0 ≤ j < i ），计算公差 d = nums[i] - nums[j] 。 若 dp[j] 中存在键 d ，说明已有以 nums[j] 结尾、公差为 d 的序列，可直接接上 nums[i] ： dp[i][d] = dp[j][d] + 1 否则，初始化以 nums[i] 结尾、公差为 d 的序列为 2（即 nums[j] 和 nums[i] 两个数）： dp[i][d] = 2 同时更新全局最大值 max_len 。 边界条件 数组长度小于 3 时，直接返回数组长度（因为两个数必构成等差数列）。 每个数本身可视为公差为 0 的等差数列（长度 1），但题目要求至少两个数，初始 max_len = 2 。 逐步计算示例 以 nums = [9, 4, 7, 2, 10] 为例： i=0 ： dp[0] 为空字典。 i=1 ： j=0 ， d = 4-9 = -5 ， dp[1][-5] = 2 ， max_len=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[3][-2] = 2 j=2 ， d = 2-7 = -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 （对应序列 [4,7] ），故 dp[4][3] = dp[2][3] + 1 = 3 ，更新 max_len=3 j=3 ， d = 10-2 = 8 ， dp[4][8] = 2 复杂度分析 时间复杂度：O(n²)，需遍历所有数对。 空间复杂度：O(n²)，最坏情况下每个 dp[i] 存储 O(n) 个公差。 总结 通过动态规划结合哈希表，高效地记录了以每个元素结尾的不同公差的等差数列长度，避免了枚举所有子序列的高复杂度。