普通: O(\(N^2\))
状态: dp[j] 表示, 以 j 结尾的最长的上升子序列
转移: dp[j]=dp[i]+1(if a[j]>a[i] )
初始化: dp[i]=1
优化 (nlogn)
solution: 维护 stack[top] 表示长度为 top 的最长子序列结尾最小的是 stack[top]
贪心 + dp
- code:
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- const int MAXX=100010;
- int a[MAXX],stack[MAXX];
- int top,n;
- int main(){
- scanf("%d",&n);
- for(int i=1;i<=n;++i)scanf("%d",&a[i]);
- for(int i=1;i<=n;++i){
- if(a[i]>stack[top])stack[++top]=a[i];
- else {
- int pos=lower_bound(stack+1,stack+top+1,a[i])-stack;
- stack[pos]=a[i];
- }
- }
- cout<<top;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2743485.html