1027. 最长等差数列
来源第 132 场周赛 Q3难度中等分数1758
题目描述
给定一个整数数组 nums,返回 nums 中最长等差子序列的长度。
注意:
- 子序列 是由另一个数组删除一些(也可以不删除)元素后得到的数组,并且不改变剩余元素之间的相对顺序。
- 如果对于所有
0 <= i < seq.length - 1,seq[i + 1] - seq[i]的值都相同,则称序列seq为等差序列。
示例 1:
输入: nums = [3, 6, 9, 12]
输出: 4
解释: 整个数组本身就是一个公差为 3 的等差序列,因此最长等差子序列为 [3, 6, 9, 12],长度为 4。
示例 2:
输入: nums = [9, 4, 7, 2, 10]
输出: 3
解释: 最长等差子序列为 [4, 7, 10](下标分别为 1、2、4),公差为 3。不存在长度为 4 的等差子序列。
示例 3:
输入: nums = [20, 1, 15, 3, 10, 5, 8]
输出: 4
解释: 最长等差子序列为 [20, 15, 10, 5](下标分别为 0、2、4、5),公差为 -5。
提示:
2 <= nums.length <= 15000 <= nums[i] <= 500
解法
方法一:动态规划
思考
枚举公差再对每个公差求最长子序列, \(n\le 1000\) 且值域在 \([0,500]\),公差种类约 \(10^3\),双重枚举下标即可在时限内完成。子序列不必连续,状态应落在「以某下标结尾、某公差」。
定义 \(f[i][j]\) 为以 \(i\) 结尾、公差为 \(j\) 的最长长度。因公差可负,将 \(j\) 平移 \(500\) 后落在 \([0,1000]\)。转移枚举 \(k<i\),用 \(f[k][j]+1\) 更新。
每个下标对更新一次,答案取所有 \(f[i][j]\) 的最大者。
我们定义 \(f[i][j]\) 表示以 \(\textit{nums}[i]\) 结尾且公差为 \(j\) 的等差数列的最大长度。初始时 \(f[i][j]=1\),即每个元素自身都是一个长度为 \(1\) 的等差数列。
由于公差可能为负数,且最大差值为 \(500\),因此,我们可以将统一将公差加上 \(500\),这样公差的范围就变成了 \([0, 1000]\)。
考虑 \(f[i]\),我们可以枚举 \(\textit{nums}[i]\) 的前一个元素 \(\textit{nums}[k]\),那么公差 \(j=\textit{nums}[i]-\textit{nums}[k]+500\),此时有 \(f[i][j]=\max(f[i][j], f[k][j]+1)\),然后我们更新答案 \(\textit{ans}=\max(\textit{ans}, f[i][j])\)。
最后返回答案即可。
如果初始时 \(f[i][j]=0\),那么我们需要在最后返回答案时加上 \(1\)。
时间复杂度 \(O(n(d + n))\),空间复杂度 \(O(nd)\)。其中 \(n\) 和 \(d\) 分别是数组 \(\textit{nums}\) 的长度以及数组 \(\textit{nums}\) 中元素的最大值与最小值的差值。
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 | |