题意：求一个波浪子序列，就是是前一半是上升子序列，后一半是下降子序列（子序列的长度必须为奇数）。
分别从左右两个方向求LIS，然后在统计最大值就行了
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<sstream> #include<cmath> #include<climits> #include<string> #include<map> #include<queue> #include<vector> #include<stack> #include<set> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define pb(a) push_back(a) #define INF 0x1f1f1f1f #define lson idx<<1,l,mid #define rson idx<<1|1,mid+1,r #define PI 3.1415926535898 void debug() { #ifdef ONLINE_JUDGE #else freopen("d:\in.txt","r",stdin); // freopen("d:\out1.txt","w",stdout); #endif } char getch() { char ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!=' ')return ch; } return EOF; } int dp1[10010],dp2[10010]; int da[10010]; int d[10010]; int work1(int n) { int maxx=0; for(int i=1;i<=n;i++) { int pos=lower_bound(d+1,d+1+maxx,da[i])-d; dp1[i]=pos; d[pos]=da[i]; maxx=max(maxx,pos); } return 0; } int work2(int n) { int maxx=0; for(int i=n;i>=1;i--) { int pos=lower_bound(d+1,d+1+maxx,da[i])-d; dp2[i]=pos; d[pos]=da[i]; maxx=max(maxx,pos); } return 0; } int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",&da[i]); int maxx=0; work1(n); work2(n); for(int i=1;i<=n;i++) { int x=min(dp1[i],dp2[i]); maxx=max(maxx,x*2-1); } printf("%d ",maxx); } return 0; }