LeetCode 1027. 最长等差数列
题目描述
题意分析
从原数组中按下标递增顺序选择若干元素，使相邻选中元素之差始终相等，返回这种等差子序列的最大长度。
选中位置可以不连续，但不能打乱顺序，因此不能先给原数组排序。公差可以为正、为负或为零；任意两个元素都能组成长度二的等差序列，不要求至少三项才计入长度。
解法：结尾位置 + 公差动态规划
核心思路
[!blue]
判断一个新元素能否接在序列后面，需要知道原序列的末项和公差。因此定义
dp[i][d]为以位置i结尾、公差为d的最长等差子序列长度。状态区分结尾位置，既确定末项数值，也保证选取顺序。枚举当前结尾
i的前一个选中位置j < i，这最后两项唯一确定公差d = nums[i] - nums[j]。若已经存在以j结尾且公差相同的序列，就可以追加当前元素，长度为dp[j][d] + 1；若不存在，j、i自身就是一个长度二的新序列。因此候选长度为
max(2, dp[j][d] + 1)。不同前驱可能产生相同的(i,d)，只保留最长的即可，因为这些序列结尾与公差相同，之后能接上的元素也完全一样，较短者不会更优。本题元素在零到五百之间，公差落在
[-500,500]。实现把公差加五百映射到0..1000，用固定宽度数组保存状态；零表示还没有长度至少二的序列。外层让结尾i递增，使用的所有j状态都已经计算完成。每条长度至少二的等差子序列都有倒数第二个位置
j，因此转移覆盖所有合法序列。枚举过程中更新全局最大值，不必强求最优序列以数组最后一项结尾。
解题步骤
- 长度不足三时，直接返回原长度。
- 创建
n × 1001的状态表，将全局答案初始化为二。- 按结尾
i递增，枚举所有更早的前驱j。- 计算偏移后的公差下标，生成延续旧序列或新建二项序列的候选长度。
- 与当前状态取最大值，并同步更新全局答案。
代码实现
class Solution {
public int longestArithSeqLength(int[] nums) {
int n = nums.length;
if (n <= 2) {
return n;
}
int[][] dp = new int[n][1001];
int ans = 2;
for (int i = 0; i < n; i++) {
// 只引用更早结尾的已完成状态行
for (int j = 0; j < i; j++) {
// 状态按结尾下标和偏移后的公差区分
int diff = nums[i] - nums[j] + 500;
// 没有旧链时，当前两项本身就是长度二的候选
int length = Math.max(2, dp[j][diff] + 1);
dp[i][diff] = Math.max(dp[i][diff], length);
ans = Math.max(ans, dp[i][diff]);
}
}
return ans;
}
}
func longestArithSeqLength(nums []int) int {
if len(nums) <= 2 {
return len(nums)
}
dp := make([][1001]int, len(nums))
ans := 2
for i := range nums {
// 只引用更早结尾的已完成状态行
for j := 0; j < i; j++ {
// 状态按结尾下标和偏移后的公差区分
diff := nums[i] - nums[j] + 500
// 没有旧链时，当前两项本身就是长度二的候选
length := dp[j][diff] + 1
if length < 2 {
length = 2
}
if length > dp[i][diff] {
dp[i][diff] = length
}
if dp[i][diff] > ans {
ans = dp[i][diff]
}
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n^2+nV)$，其中 $V=1001$。枚举位置对为 $O(n^2)$，初始化状态表为 $O(nV)$；固定本题数值范围时可简记 $O(n^2)$。
- 空间复杂度：$O(nV)$，保存每个结尾、每种公差的最优长度。
关键点总结
[!green]
- 末项与公差共同决定未来的可接续条件，缺少任一维都会混淆状态。
- 未有旧序列时，任意两个位置自然建立长度二的起点。
- 相同结尾、公差下只保留最长序列，不会影响以后求最优。
- 公差偏移只改变存储下标，不改变原数组顺序或数值。
易错点总结
[!yellow]
- 直接用负公差作为数组下标会越界，需要统一加五百。
- 只记录每个位置的最长长度，会将不同公差的序列错误地接在一起。
- 将默认零状态简单加一，只得到长度一，漏掉当前两个元素已经组成的合法起点。
- 不限制
j < i或先排序，会破坏子序列必须保持原下标顺序的条件。- 只返回最后一行状态会漏掉提前结束的最优子序列，应维护全局最大值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 同样求最长子序列，本题延续还受固定公差约束，需要按末项和公差保存状态。 |
| 446. 等差数列划分 II - 子序列 | 困难 | 状态维度相同，原题计全部等差子序列，本题只保留最长长度。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！