最长等差子序列如何用动态规划求解？为什么状态里要带公差？

简化版

最长等差子序列需要把公差放进状态。定义 dp[i][diff] 表示以 nums[i] 结尾、公差为 diff 的最长等差子序列长度。枚举前一个位置 j<i，令 diff=nums[i]-nums[j]，转移为 dp[i][diff] = max(dp[i][diff], dp[j][diff] + 1)。

详细版

因为同一个结尾元素可能属于不同公差的等差序列，只用 dp[i] 无法表达。每个位置维护一个哈希表，键是公差，值是对应最长长度。若 dp[j][diff] 不存在，说明可以由 nums[j], nums[i] 组成长度 2 的序列。

时间复杂度 O(n²)，空间复杂度 O(n²)。实现时要注意公差可能为负，也可能超出 int 范围，稳妥写法可以用 long 存 diff。

完整版教学

一、为什么普通 LIS 状态不够

最长递增子序列只关心大小关系，而等差子序列还要求相邻差值固定。例如同样以数字 7 结尾，它可能接在公差 2 的序列后，也可能接在公差 3 的序列后。

1, 3, 5, 7  公差 2
1, 4, 7     公差 3

如果只写 dp[i] = 以 i 结尾的最长长度，这两个信息会被混在一起，后面无法判断能否继续接。

二、状态为什么要带 diff

定义：

dp[i][diff] = 以 nums[i] 结尾，且公差为 diff 的最长等差子序列长度

这里 i 固定结尾，diff 固定序列规则。只有这两个维度都确定，才能判断新元素是否能接上。

维度	作用
`i`	确定序列最后一个元素
`diff`	确定等差规则
值	记录最长长度

记忆钩子：子序列的“规则”如果会影响后续连接，就要进入 DP 状态。

三、转移公式怎么推

枚举一对下标 j < i，它们可以形成一个公差：

diff = nums[i] - nums[j]

如果之前已经有以 j 结尾、公差为 diff 的序列，就把 nums[i] 接上：

dp[i][diff] = dp[j][diff] + 1

如果没有，则至少可以组成长度 2：

dp[i][diff] = 2

实际代码里常写成 prev + 1，其中 prev 默认 1。

四、用数字例子推演

看数组 [3, 6, 9, 12]：

i=1, j=0, diff=3 => dp[1][3]=2
i=2, j=1, diff=3 => dp[2][3]=dp[1][3]+1=3
i=3, j=2, diff=3 => dp[3][3]=dp[2][3]+1=4

答案是 4。再看 [9,4,7,2,10]，公差可以是负数、正数，不要假设数组递增。

4,7,10 公差 3，长度 3

五、代码模板

int longestArithSeqLength(int[] nums) {
    int n = nums.length;
    Map<Long, Integer>[] dp = new HashMap[n];
    for (int i = 0; i < n; i++) dp[i] = new HashMap<>();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            long diff = (long) nums[i] - nums[j];
            int len = dp[j].getOrDefault(diff, 1) + 1;
            dp[i].put(diff, Math.max(dp[i].getOrDefault(diff, 0), len));
            ans = Math.max(ans, dp[i].get(diff));
        }
    }
    return ans;
}

getOrDefault(diff, 1) 的含义是：如果 j 之前没有同公差序列，就把 nums[j] 当作长度 1 的起点，加上 nums[i] 后长度为 2。

六、公差范围和数组下标优化

有些题目约束 nums[i] 范围较小，可以用数组偏移存公差，例如 diff + 500。但通用写法用哈希表更安全。

存储方式	适用场景	风险
数组偏移	数值范围小且已知	容易越界
HashMap	diff 范围大或未知	常数开销更高

如果 nums[i] 接近 Integer.MAX_VALUE 和 Integer.MIN_VALUE，diff 用 int 可能溢出，使用 long 更稳。

七、常见误区与追问

误区：只用一维 dp[i]。 同一结尾可能对应多个公差，必须区分。
误区：认为公差只能为正。 子序列不要求递增，公差可以为负或 0。
误区：不存在历史状态时从 0 开始。 两个数本身就能组成长度 2 的等差序列。
追问：为什么时间复杂度是 O(n²)？ 要枚举所有有序二元组 (j,i)。
追问：能不能排序后做？ 不能随意排序，子序列必须保持原数组相对顺序。
追问：公差为 0 怎么处理？ 哈希表键可以是 0，表示多个相同数字组成的等差序列。

八、加强记忆

最长等差子序列的关键不是“最长”，而是“等差规则要跟着状态走”。以 i 结尾还不够，还要带上 diff，否则后面不知道能不能继续接。枚举 j<i 形成公差，从 dp[j][diff] 接到 dp[i][diff]；没有历史就从长度 2 开始。

简化版

详细版