如果不存在这样的 `k`，则 `dp[i][j] = 2`（至少包含 `nums[i]` 和 `nums[j]` 两个元素）。  

线性动态规划：最长等差数列的长度（进阶版——允许公差为零） 题目描述 给定一个整数数组 nums ，返回该数组中最长等差数列子序列的长度。等差数列子序列是指一个子序列（元素顺序与原数组一致，但不一定连续）中，任意相邻两项的差相等。与基础版不同，本题允许公差为零，即所有元素相同的子序列也被视为等差数列。例如，数组 [3, 6, 9, 12] 的最长等差数列子序列为 [3, 6, 9, 12] ，长度为 4；数组 [1, 1, 1, 1] 的最长等差数列子序列为整个数组，长度为 4。 解题过程 问题分析 目标：在整数数组中找到最长的等差数列子序列（允许公差为零）。 难点：等差数列的公差可能为任意整数（包括零），且子序列不要求连续。 动态规划思路：定义状态 dp[i][d] 表示以第 i 个元素结尾、公差为 d 的最长等差数列子序列的长度。但公差 d 可能非常大，直接作为数组下标不现实。需优化状态表示。 状态定义优化 使用二维数组 dp[i][j] ：表示以 nums[i] 和 nums[j] 作为最后两个元素的等差数列子序列的最大长度（其中 i < j ）。 公差 d = nums[j] - nums[i] 。对于固定的 j ，遍历所有 i < j ，通过公差 d 找到前驱元素 prev = nums[i] - d 的位置 k （ k < i ），从而更新状态。 状态转移方程： \[ dp[ i][ j] = dp[ k][ i] + 1 \quad (\text{如果存在 } k < i \text{ 使得 } nums[ k] = nums[ i ] - d) \] 如果不存在这样的 k ，则 dp[i][j] = 2 （至少包含 nums[i] 和 nums[j] 两个元素）。 最终答案：所有 dp[i][j] 中的最大值。 处理公差为零的情况 当公差为零时，等差数列要求所有元素相同。此时需单独记录每个数值的出现次数。 优化：在遍历前，先统计数组中每个数值的频率，最大频率即为公差为零时的最长等差数列长度。最终结果取最大值时需包含此情况。 算法步骤 初始化： 若数组长度 ≤ 2 ，直接返回数组长度（任何两个元素都构成等差数列）。 创建二维数组 dp[n][n] （ n 为数组长度），初始值均为 2。 创建哈希表 freq 统计每个数值的频率，记 maxFreq 为最大频率。 双层循环： 外层遍历 j 从 2 到 n-1 （因为至少需要两个元素）。 内层遍历 i 从 0 到 j-1 ： 计算公差 d = nums[j] - nums[i] 。 寻找前驱元素 target = nums[i] - d 的位置 k （ k < i ）。 若找到 k ，则 dp[i][j] = dp[k][i] + 1 ；否则保持 dp[i][j] = 2 。 结果：取 maxFreq 和所有 dp[i][j] 中的最大值。 复杂度分析 时间复杂度：O(n²)，双层循环遍历所有 (i, j) 对。 空间复杂度：O(n²)，用于存储 dp 数组。 示例 数组 nums = [1, 2, 3, 4, 5, 6] ： 公差为 1 的等差数列 [1, 2, 3, 4, 5, 6] 长度为 6。 数组 nums = [1, 1, 1, 2, 3] ： 公差为零时， [1, 1, 1] 长度为 3；公差为 1 时， [1, 2, 3] 长度为 3。最终结果为 3。 通过以上步骤，可高效求解允许公差为零的最长等差数列子序列问题。