最长上升子序列(LIS)
序列 最长 上升 LIS
2023-09-11 14:22:48 时间
O(n^2)算法
dp[i] 以a[i]结尾的最长上升子序列
1· 只包含a[i] (1)
2· 在J<I 且 a[J]<a[I] dp[I]=dp[J]+1
状态转移方程
dp[I]=max (1, dp[J]+1| J<I且 a[J]<a[J])
算法模板
//O(n^2)
#include <cstdio>#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 30010;
int dp[maxn], a[maxn];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;++i)
scanf("%d",&a[i]);
int ans=0;
for(int i=0;i<n;++i)
{
dp[i]=1;
for(int j=0;j<i;++j)
{
if(a[j]<a[i])
dp[i] = max(dp[i], dp[j]+1); //状态转化方程
}
ans=max(dp[i],ans);
}
printf("%d\n",ans);
}
return 0;
}
O(nlogn)算法
dp[i] i表示长度为i+1的末尾元素最小值
初始化 dp[i] = INF
a[j] i=0 ap[i-1]<a[j] dp[i]=min()
INF | INF | INF | INF | INF |
#include <cstdio>
#include <algorithm>
#define INF 0x3f3f3f
using namespace std;
int dp[30010],a[30010];
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;++i)
{
scanf("%d",&a[i]);
dp[i]=INF;
}
for(i=0;i<n;++i)
*lower_bound(dp,dp+n,a[i])=a[i];
printf("%d\n",lower_bound(dp,dp+n,INF)-dp);
}
return 0;
}
相关文章
- 最长上升子序列(总结)
- Java 第十一届 蓝桥杯 省模拟赛 正整数的摆动序列
- Java实现 LeetCode 594 最长和谐子序列(滑动窗口)
- Java实现 LeetCode 516 最长回文子序列
- Java实现 LeetCode 300 最长上升子序列
- Java实现 LeetCode 128 最长连续序列
- Lintcode--010(最长上升子序列)
- 799. 最长连续不重复子序列
- 剑指 Offer II 119. 最长连续序列
- 最长上升子序列(线性DP)
- 【7001】n阶法雷序列
- 【u023】最长上升子序列(sequence)
- 编程笔试(解析及代码实现):序列重排之给一个长度为n的序列A,求找出某种排列方式使得相邻两个数的差值之和最大并求出该最大值
- 解读ICDE‘22论文:基于鲁棒和可解释自编码器的无监督时间序列离群点检测算法
- 【关于时间序列的ML】项目 5 :用机器学习预测天气
- 【数字信号处理】相关系数 ( 相关系数概念解析 | 信号能量常数 | 共轭序列 | 序列在相同时刻的相关性 )
- 【数字信号处理】序列傅里叶变换 ( 基本序列的傅里叶变换 | 求 a^nu(n) 的傅里叶变换 )
- 最长上升子序列
- 最长回文子序列
- 【洛谷】P1439 【模板】求最长公共子序列
- 买卖股票的最佳日期,使用动态规划解决最长上升子序列的问题