【算法】【动规】最长定差子序列,大数组优化!!
2023-12-20 18:32:26
跳转汇总链接
优化在后面!
2.5 最长定差子序列
给你一个整数数组 arr 和一个整数 difference,请你找出并返回 arr 中最长等差子序列的长度,该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下,通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
- 状态表示
- dp[i] 表示,以 i 位置元素为结尾的所有子序列中,最长子序列的长度
- 状态转移方程
- 略(简单,不清楚的可以翻看之前的题解)
- 初始化
- 略
- 填表顺序
- 略
- 返回值
- 略
说的通但跑不通的代码:
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
int n = arr.size();
vector<int> dp(n, 1);
int retMax = 1;
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
if(arr[i] - arr[j] == difference)
{
dp[i] = dp[j] + 1;
}
}
retMax = max(retMax, dp[i]);
}
return retMax;
}
};
写到这里本人都以为只是一个练手题
…
直到
…
…
…
只好拿出 hash,再来一遍
- 优化
- 将 <arr[]元素, dp[]> 的值绑定放在 hash 表中
- 直接在 hash 中进行动态规划操作
🐎代码如下:
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
unordered_map<int, int> hash; // arr, dp
hash[arr[0]] = 1; // 初始化
int retMax = 1;
for(int i = 1; i < arr.size(); i++)
{
hash[arr[i]] = hash[arr[i] - difference] + 1;
retMax = max(retMax, hash[arr[i]]);
}
return retMax;
}
};
🥰如果本文对你有些帮助,欢迎👉 点赞 收藏 关注,你的支持是对作者大大莫大的鼓励!!(????) 若有差错恳请留言指正~~
文章来源:https://blog.csdn.net/m0_67470729/article/details/135110502
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!