线性动态规划：最长等差数列 题目描述 给定一个整数数组 nums，返回数组中最长等差数列的子序列长度。等差数列是指数组中一个子序列（不要求连续），其中任意相邻两个元素的差相等。例如，对于数组 [ 3,6,9,12,15,18]，其本身就是一个等差数列，长度为6。对于数组 [ 9,4,7,2,10,8]，最长的等差数列是 [ 4,7,10] 和 [ 4,2,8 ]（差分别为3和-4），长度均为3。 解题过程 问题分析 我们需要找到一个最长的子序列（注意：是子序列，不是子数组，所以元素可以不连续），使得这个子序列中任意相邻两个元素的差值都相同。这个相同的差值我们称之为公差。一个序列本身（只有一个元素）可以视为公差为任意值的等差数列。 动态规划状态定义 这是本题的核心。一个直观但错误的想法是定义 dp[i] 为以 nums[i] 结尾的最长等差数列的长度。然而，这样定义缺少了一个关键信息：公差。对于同一个结尾 nums[i] ，如果来自不同的前驱元素，它们构成的公差可能是不同的。 例如，数组为 [ 1, 3, 5, 7, 5, 3, 1 ]。 以最后一个元素 1 结尾： 如果前驱是 3 ，公差是 1-3 = -2。 如果前驱是 5 ，公差是 1-5 = -4。 这两种情况对应的最长等差数列长度是不同的。 因此，我们的状态需要包含两个维度： 序列的结尾索引 i 和 公差 diff 。 我们定义 dp[i][diff] 表示以索引 i 结尾，且公差为 diff 的最长等差数列的长度。 状态转移方程 我们的目标是填充 dp[i][diff] 。对于当前位置 i ，我们如何得到以它结尾的等差数列？ 我们需要枚举 i 之前的所有位置 j (0 <= j < i)。 对于每一对 (j, i) ，我们可以计算出一个公差 diff = nums[i] - nums[j] 。 那么，以 i 结尾、公差为 diff 的等差数列，就可以由以 j 结尾、公差也为 diff 的等差数列接上 nums[i] 而来。 所以，状态转移方程为： dp[i][diff] = dp[j][diff] + 1 但是，这里有一个边界情况：如果我们在 j 处找不到以 j 结尾、公差为 diff 的等差数列怎么办？这意味着目前只有 nums[j] 和 nums[i] 两个元素构成了一个公差为 diff 的等差数列。任何两个数都能构成一个等差数列，所以初始长度应为 2。 因此，更通用的状态转移方程是： dp[i][diff] = dp[j].get(diff, 1) + 1 解释：我们尝试从 dp[j] 这个字典（或Map）中获取键为 diff 的值。如果存在，说明之前已经有以 j 结尾、公差为 diff 的序列，我们就在其长度基础上加1。如果不存在（ get(diff, 1) 会返回默认值1），说明目前只有 nums[j] 这一个元素（长度为1），加上 nums[i] 后构成一个长度为2的新序列。 初始化 对于数组中的每个位置 i ，至少可以和自己构成一个长度为1的等差数列（公差任意）。但通常我们不需要显式初始化长度为1的情况，因为在状态转移时，当我们使用 dp[j].get(diff, 1) ，这个 1 就已经隐含了初始化。我们只需要将最终答案的初始值设为1（因为最短的等差数列长度就是1，即单个元素）。 计算顺序与结果提取 我们使用两层循环。外层循环 i 从 0 到 n-1，遍历每个位置作为序列的结尾。 内层循环 j 从 0 到 i-1，遍历 i 之前的所有可能的前驱位置。 对于每一对 (j, i) ，计算公差 diff = nums[i] - nums[j] 。 根据状态转移方程更新 dp[i][diff] 。 同时，在每次更新 dp[i][diff] 后，我们用 max(ans, dp[i][diff]) 来更新全局最长长度 ans 。 复杂度分析 时间复杂度：O(n²)，其中 n 是数组长度。因为有两层嵌套循环。 空间复杂度：O(n²)。在最坏情况下，每个索引 i 对应的字典可能存储 O(n) 个不同的公差（例如数组元素都不同时），所以总空间复杂度为 O(n²)。 总结 这个问题的关键在于识别出状态需要包含“公差”这一维度，从而能够区分以同一个元素结尾但公差不同的各种等差数列情况。通过枚举前驱节点并利用哈希表（或字典）来高效存储和查找不同公差对应的序列长度，我们可以有效地解决这个问题。