Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #define N 100001
- using namespace std;
- int d[N],k; /// d[i]=capatul celui de-al i-lea subsir
- void CautBin(int x)
- {
- if(x<=d[k])
- {
- d[++k]=x;
- return ;
- }
- int st,dr,p,mid;
- p=st=1;dr=k;
- while(st<=dr)
- {
- mid=(st+dr)/2;
- if(d[mid]<x)
- p=mid,dr=mid-1;
- else
- st=mid+1;
- }
- d[p]=x;
- }
- int main()
- {
- int n,x;
- cin>>n>>x;
- d[1]=x;
- k=1;
- for(int i=2;i<=n;++i)
- cin>>x,CautBin(x);
- cout<<k<<'\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement