题目链接：http://acmoj.shu.edu.cn/problem/415/ 题意： 题目是中文，很容易理解 规模： n:[1,5e5] 类型： 简单Lis,nlongn算法
分析： 这道题是很明显的，lis最长上升子序列，看看复杂度，nlogn没问题，思路就是左扫一遍，右扫一遍，两边的长度取较小
时间复杂度&&优化： nlogn 代码：
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<stack> #include<math.h> #include<vector> #include<algorithm> #include<iostream> using namespace std; const int MAXN = 500005; const int MAXM = 5005; const int inf = 1000000007; const int mod = 1000000007; int n,m; int a[MAXN]; int lenl[MAXN],lenr[MAXN]; int dp[MAXN]; void lis(){ memset(dp,0,sizeof(dp)); int len=1; dp[0]=a[0]; for(int i=1;i<n;i++){ int pos=lower_bound(dp,dp+len,a[i])-dp; dp[pos]=a[i]; len=max(len,pos+1); lenl[i]=len; } memset(dp,0,sizeof(dp)); len=1; dp[0]=a[n-1]; for(int i=1;i<n;i++){ int pos=lower_bound(dp,dp+len,a[n-1-i])-dp; dp[pos]=a[n-1-i]; len=max(len,pos+1); lenr[n-1-i]=len; } } int main() { while(cin>>n){ memset(a,0,sizeof(a)); memset(lenl,0,sizeof(lenl)); memset(lenr,0,sizeof(lenr)); memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++){ cin>>a[i]; } lis(); int maxn=0; for(int i=0;i<n;i++){ maxn=max(maxn,min(lenl[i],lenr[i])); } cout<<maxn*2-1<<endl; } return 0; }