文章目录
题目
一、解题思路
二、结果
1.注意点
2.C++代码
总结
题目
给你一个整数数组 arr 和一个整数 difference,请你找出并返回 arr 中最长等差子序列的长度,该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下,通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
示例 1:
输入:arr = [1,2,3,4], difference = 1
输出:4
解释:最长的等差子序列是 [1,2,3,4]。
示例 2:
输入:arr = [1,3,5,7], difference = 1
输出:1
解释:最长的等差子序列是任意单个元素。
示例 3:
输入: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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference
一、解题思路
假设给定数组为 [1,5,3,6,5,7],等差 d=2,辅助数组为 dp,求解的过程如下:
遍历到 1,发现 1-2=-1 不在 dp 数组,记录 dp[1] = 1,表示以 1 结尾的等差数列只有 1 个数;
遍历到 5,发现 5-2=3 不在 dp 数组,记录 dp[5]=1;
遍历到 3,发现 3-2=1 在 dp 数组且以 1 结尾的等差数列长度为 1,所以,记录 dp[3]=dp[3-2]+1=2,表示以 3 结尾的等差数列长度为 2;
遍历到 6,发现 6-2=4 不在 dp 数组,记录 dp[6]=1;
遍历到 5,发现 5-2=3 在 dp 数组,记录 dp[5]=dp[5-2]+1=3;
遍历到 7,发现 7-2=5 在 dp 数组,记录 dp[7]=dp[7-2]+1=4;
取 dp 数组中的最大值,即 4,所以,最长等差子序列的长度为 4。
这其实就是动态规划的递推过程,所以,我们可以定义动态规划如下:
状态定义:dp[x] 表示以 x 结尾的最长等差子序列的长度;
状态转移:dp[x]=dp[x-d]+1;
二、结果
1.注意点
利用辅助数组存储序列等差项的个数;
注意理解dp[x]=dp[x-d]+1的推到,存在一个等差的就+1;
2.C++代码
代码如下(示例):
class Solution {
public:
int longestSubsequence(vector<int> &arr, int difference) {
int ans = 0;
//创建dp数组来记录序列的个数
unordered_map<int, int> dp;
for (int v: arr) {
dp[v] = dp[v - difference] + 1;
ans = max(ans, dp[v]);
}
return ans;
}
};
总结
题目完全可以用暴力去解决,但可能会超时,动态规划很难想到,要不断吸取经验,熟能生巧!!
加油加油,坚持坚持!!!