(算法)最长递增子序列
问题:
Given an array of N integer, find the length of the longest increasing subsequence.
For example, given [1,-5,4,5,10,-1,-5,7], the longest increasing subsequence is length 4.(1,4,510)
思路:
1、枚举
枚举数组所有的子序列,然后判断它们是否为递增子序列(回溯法)。
2、转化
将数组排序,然后找出新数组和旧数组的最长公共子序列LCS。
(关于最长公共子序列,参考:http://www.cnblogs.com/AndyJee/p/4469196.html)
3、动态规划
假设数组为A,len[i] 表示以第 i 个元素为结尾(即第i个元素为最大)的最长递增子序列的长度;
求len[i],可以先求以前面i-1个元素结尾的最长递增子序列,如果A[i]比前面A[0...i-1]中某个元素k小,那么就可以在相应的len[k]上加1,当然是最大的len[k];
详见http://blog.csdn.net/kenby/article/details/6804720
4、优化
上述方法在求len[i]的时候, 要从a[1], ... a[i-1]中找出所有比 a[i] 小的元素,而a[1], ... a[i-1]是无序的,查找速度比较慢。
引出数组 f[k] 表示长度等于k的递增子序列中最末尾的元素, 长度越长的序列,其末尾元素也越大,所以f[k]是递增的。
实例 <1, 3, 4, 2, 7>
len[1] = 1, f[1] = a[1] = 1
len[2] = 2, f[2] = a[2] = 3
len[3] = 3, f[3] = a[3] = 4
len[4] = 2, f[2] = a[4] = 2 ( 更新了f[2] )
那么,如何求len[5] 呢?
f[1] = 1, f[2] = 2, f[3] = 4, a[5] = 7,
找出末尾元素比a[5]小,而且长度最长的递增子序列,此例中,
f[3] = 4 表示长度等于3的子序列,其末尾元素为4,这个子序列的长度最长。
a[5]加上此序列形成的新序列长度为4, 然后更新f[4] = a[5] = 7,表示长度等于4的子序列,其末尾元素等于7
在上面的步骤中,找出末尾元素比a[i]小,而且长度最长的子序列,其实就是对于f[1], ...f[k], 从后往前找,第一个比a[i]小的元素就是长度最长的子序列。查找的时候可以用二分查找方法,故更快。
代码:
1、动态规划
#include <iostream> #include <vector> using namespace std; unsigned int LISS(const int array[], size_t length, vector<int> &result) { unsigned int liss[length]; unsigned int pre[length]; for(int i=0;i<length;++i){ liss[i]=1; pre[i]=i; } int k=0; int max=1; for(int i=1;i<length;++i){ for(int j=0;j<i;++j){ if(array[j]<array[i] && liss[j]+1>liss[i]){ liss[i]=liss[j]+1; pre[i]=j; if(max<liss[i]){ max=liss[i]; k=i; } } } } // i = max - 1; while(pre[k]!=k){ // result[i--] = array[k]; result.push_back(array[k]); k=pre[k]; } //result[i] = array[k]; result.push_back(array[k]); return max; } int main() { int A[]={1,-5,4,5,10,-1,-5,7}; int len=sizeof(A)/sizeof(A[0]); vector<int> result; cout << LISS(A,len,result) << endl; for(int i=0;i<result.size();i++) cout<<result[i]<<' '; cout<<endl; }
2、优化
#include <iostream> #include <vector> using namespace std; unsigned int LISS(const int array[], size_t length, vector<int> &result) { unsigned int liss[length]; unsigned int pre[length]; unsigned int f[length]; for(int i=0;i<length;++i){ liss[i]=1; pre[i]=i; f[i]=0; } int k=0; int max=1; f[max]=0; for(int i=1;i<length;++i){ for(int j=max;j>=1;--j){ if(array[f[j]]<array[i]){ liss[i]=j+1; pre[i]=f[j]; if(f[liss[i]]!=0){ int old=array[f[liss[i]]]; if(array[i]<old) f[liss[i]]=i; } else f[liss[i]]=i; if(max<liss[i]){ max=liss[i]; k=i; } break; } } } // i = max - 1; while(pre[k]!=k){ // result[i--] = array[k]; result.push_back(array[k]); k=pre[k]; } //result[i] = array[k]; result.push_back(array[k]); return max; } int main() { int A[]={1,3,4,2,7}; int len=sizeof(A)/sizeof(A[0]); vector<int> result; cout << LISS(A,len,result) << endl; for(int i=0;i<result.size();i++) cout<<result[i]<<' '; cout<<endl; }
在线测试OJ:
http://www.nowcoder.com/questionTerminal/585d46a1447b4064b749f08c2ab9ce66
AC代码:
class AscentSequence { public: int findLongest(vector<int> A, int n) { vector<int> dp(n); vector<int> f(n); dp[0]=1; f[0]=A[0]; int left,right,mid; int count=0; int lmax=1; for(int i=1;i<n;i++){ left=0; right=count; while(left<=right){ mid=left+((right-left)>>1); if(A[i]>=f[mid]) left=mid+1; else right=mid-1; } f[left]=A[i]; if(left>count) count=left; dp[i]=left+1; if(lmax<dp[i]) lmax=dp[i]; } return lmax; } };
class AscentSequence { public: int findLongest(vector<int> A, int n) { int len=A.size(); if(len<=1) return len; vector<int> mLen(n,1); int lMax=1; for(int i=1;i<n;i++){ for(int j=0;j<i;j++){ if(A[i]>A[j] && mLen[j]+1>mLen[i]) mLen[i]=mLen[j]+1; if(mLen[i]>lMax) lMax=mLen[i]; } } return lMax; } };
相关文章
- 【建议收藏】时间序列预测paper、应用汇总
- 「CSP-J/S2022模拟赛7.12 D」来 / YbtOJ 「分块算法」历史序列
- 2022-09-19:给定字符串 S and T,找出 S 中最短的(连续)子串 W ,使得 T 是 W 的 子序列 。 如果 S 中没有窗口可以包含 T 中的
- 由遍历序列构造二叉树--王道
- 环状序列
- 每日一题(组队竞赛,排序子序列,倒置字符串, 删除公共字符,修理牧场)
- 【人体运动生成】开源 | 第一个能够从自然语言或音频序列生成人体动作序列的统一驱动引擎UDE,性能SOTA!
- 基于SARIMA、XGBoost和CNN-LSTM的时间序列预测对比
- 寻找变化前的01序列
- 一个基于序列的弱监督视觉信息抽取学习框架
- BAT面试算法进阶(10)- 最长的斐波那契子序列的长度(暴力法)
- 【干货书】时间序列算法导论:使用Python实现机器学习和深度学习技术
- 【数字信号处理】周期序列 ( 周期序列示例 2 | 模拟信号周期 | 数字信号周期 | 在 a 个模拟信号周期内采集 b 个数字信号采样 )
- 【数字信号处理】傅里叶变换性质 ( 共轭对称、共轭反对称 与 偶对称、奇对称关联 | 序列对称分解定理 )
- 2023-04-03:如何使用滑动窗口算法和回溯算法解决亚马逊面试题——最长连续相同元素子序列问题?
- Oracle 取序列值的高效解决方案(oracle取序列值)
- 最长回文子序列算法详解编程语言
- 查看Oracle数据库中的序列(oracle查看序列)
- Oracle中的自增序列:运用与数据库中.(oracle递增序列)
- Oracle中如何查询序列的方法(oracle如何查询序列)
- Oracle产生序列一种有效率的解决方案(oracle 产生序列)
- Oracle10g建立序列的指导(oracle10g建序列)
- php数组函数序列之array_search()-按元素值返回键名