最长上升子序列
序列 最长 上升
2023-09-27 14:26:02 时间
1、O(n^2)复杂度
dp转移方程:
dp[i]=max(dp[i],dp[j]+1)(j<i && dp[i]>dp[j])
代码:
#include<iostream>
using namespace std;
int i,j,n,a[100],b[100],max;
int main()
{
cin>>n;
for(i=0;i<n;i++) cin>>a[i];
b[0]=1; //初始化,以a[0]结尾的最长递增子序列长度为1
for(i=1;i<n;i++)
{
b[i]=1;//b[i]最小值为1
for(j=0;j<i;j++)
if(a[i]>a[j]) b[i]=max(b[i],b[j]+1);
}
for(max=i=0;i<n;i++) if(b[i]>max) max=b[i];
cout<<max<<endl;
}
2、O(n*logn)复杂度
每次取栈顶元素和读到的元素做比较,如果大于栈顶元素,则将它入栈;如果小于,则二分查找栈中的比它大的第1个数,并替换它。最长序列长度即为最后模拟的大小。
这也是很好理解的,对于i和j,如果i <j且a[i] < a[j],用a[i]替换a[j],长度虽然没有改变但a的'潜力'增大了。
#include <iostream>
using namespace std;
int i,j,n,s,t,a[100001];
int main()
{
cin>>n;
a[0]=-1000000;
for(i=0;i<n;i++)
{
cin>>t;
if(t>a[s]) a[++s]=t;
else
{
int l=1,h=s,m;
while(l<=h)
{
m=(l+h)/2;
if(t>a[m]) l=m+1;
else h=m-1;
}
a[l]=t;
}
}
cout<<s<<endl;
}
可能有人不清楚为什么二分找到栈中某个位置之后,并把这个值替换,但是为什么栈的长度s为什么没有回退。因为s保存的是最后的答案,所以这其实没有造成影响
相关文章
- JZ31. 栈的压入、弹出序列
- LeetCode376摆动序列 c++贪心
- AI-蛋白质-序列设计-从头设计-2022:ProteinMPNN(消息传递图神经网络)【根据蛋白质结构“逆推”出可能的氨基酸序列(序列恢复率52%)】【传统方法是通过调整自然界中已知的蛋白质】
- 最长公共子序列
- 最长公共上升子序列
- 题目1533:最长上升子序列 (nlogn | 树状数组)
- HDU 4604 Deque 二分最长上升子序列
- 九度oj-1533 最长上升子序列 (LIS)
- zoj1003-Max Sum (最大连续子序列之和)
- 动态规划法——最长公共子序列问题
- LeetCode_动态规划_中等_673.最长递增子序列的个数
- leetcode300 最长上升子序列
- leetcode128 最长连续序列
- 数据结构(C++版)——栈的应用,利用栈的先进后出判断一个包含“(“和“)“ “[“和“]“ “<“和“>“ “{“和“}“的括号序列是否匹配
- 895. 最长上升子序列
- AcWing 272. 最长公共上升子序列
- AcWing 1016. 最大上升子序列和
- AcWing 895. 最长上升子序列
- [LeetCode] 659. Split Array into Consecutive Subsequences 将数组分割成连续子序列
- C# 序列类为 xml 可以使用的特性大全