题目描述
给你一个整数数组 arr
和一个整数 difference
,请你找出 arr
中所有相邻元素之间的差等于给定 difference
的等差子序列,并返回其中最长的等差子序列的长度。
样例
输入:arr = [1,2,3,4], difference = 1
输出:4
解释:最长的等差子序列是 [1,2,3,4]。
输入:arr = [1,3,5,7], difference = 1
输出:1
解释:最长的等差子序列是任意单个元素。
输入:arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出:4
解释:最长的等差子序列是 [7,5,3,1]。
1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4
算法
(DP) $O(n)$
- f[i]表示以arr[i]结尾的最长定差子序列
$f[i] = f[j] + 1$ , 存在j ∈ [0, i-1]中有arr[j] == arr[i] - difference
$f[i] = 1$, 不存在j ∈ [0, i-1]中有arr[j] == arr[i] - difference
解释:
对于每个状态来说,如果在之前出现过j ∈ [0, i-1]
中有arr[j] == arr[i] - difference
,说明arr[i]是接在arr[j]的后面的(他们两个相差difference),所以以arr[i]结尾的最长定差子序列的长度(即f[i]
) 是为 以arr[j]结尾的最长定差子序列的长度(即f[j]
)加上1。 即得 $f[i] = f[j] + 1$
C++ 代码
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
int n = arr.size();
if(n == 1) return 0; // 数组长度为1的时候,是没有最长定差子序列的。
vector<int> f(n+5); // f[i]表示以arr[i]结尾的最长定差子序列
unordered_map<int, int> memo; // 记录已经存在的状态,有助于快速查找已有状态
int res = 0;
for (int i = 0; i < n; i++) {
if (i == 0) memo[arr[0]] = 1; // 虽然f[0]应该是0才对,但是后面状态需要依赖此状态在开头已经特判了n==1的情况了
else {
f[i] = 1; // f[i]最小为1
if (memo.find(arr[i] - difference) != memo.end()) // 若之前出现了arr[i] - difference,就是在之前状态的基础上长度 + 1
f[i] = max(f[i], memo[arr[i] - difference] + 1);
memo[arr[i]] = f[i];
}
res = max(res, f[i]); // 记录最长的定差子序列是多少
}
return res;
}
};
PS: 官方测试用例有错arr为[1], difference为1的时候 答案应该为0。官网测试用例预测给的是1
意思应该是不管咋样,至少长度为1 因为没有第二个数去check difference