我这个代码不是nlogn吗???

回复帖子 返回题目

@ uhgariej 2017-10-12 22:35

//第一问求最长不上升子序列,我是反过来求得(所以和第二问差不多就是upper_bound和lower_bound区别)

//第二问求最长上升子序列
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL; 
const int maxn=1e5+10;
int d1[maxn],d2[maxn];
int A[maxn]; 
int main(){
//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout);
    cin.sync_with_stdio(false);
     int tmp,n=0,ans=-1e9;
    while(cin>>tmp)
         A[++n]=tmp; 
    fill(d1+1,d1+1+n,1e9);
    for(int i=n;i>=1;--i)
        *upper_bound(d1+1,d1+1+n,A[i])=A[i];
    cout<<lower_bound(d1+1,d1+1+n,1e9)-(d1+1)<<endl;  //第一问
     fill(d2+1,d2+1+n,1e9);
     for(int i=1;i<=n;++i)
         *lower_bound(d2+1,d2+1+n,A[i])=A[i];    
    cout<<lower_bound(d2+1,d2+1+n,1e9)-(d2+1)<<endl;  //第二问
//    cout<<"Time used = "<<static_cast<double>(clock())/(CLOCKS_PER_SEC)<<"s"<<endl;
    return 0;
}
@ rose_ 2017-10-18 12:58 回复

我怎么看都像是n方,请无视我这个新手》》》》》