描述
如果一个序列有奇数个正整数组成，不妨令此序列为 a1,a2,a3,...,a2∗k+1 ( 0<=k )，并且 a1,a2...ak+1 是一个严格递增的序列， ak+1,ak+2,...,a2∗k+1 ,是一个严格递减的序列，则称此序列是A序列。
比如1 2 5 4 3就是一个A序列。
现在Jazz有一个长度为 n 的数组，他希望让你求出这个数组所有满足A序列定义的子序列里面最大的那个长度。（子序列可以不连续）
比如1 2 5 4 3 6 7 8 9，最长的A序列子串是1 2 5 4 3。
输入多组输入，每组两行。 第一行是 n ，表示给的数组的长度。 第二行有 n 个数(int范围)，即给你的数组。 1<=n<=500000 。
输出每组输入输出一行，即最长的A序列子串的长度。
样例输入1 复制 9 1 2 5 4 3 6 7 8 9 样例输出1 5开始犯了一个sb错误，没看见是子序列，
后来又犯一个sb错误，没看见峰值左右长度对称。
很简单，就是把原序列和原序列的反转序列都求一遍最长上升子序列，
然后美剧一下即可。
#include<iostream> #include<stdio.h> #include<string.h> #define ll long long using namespace std; const int maxn=500005; int a[maxn]; int b[maxn],c[maxn],d[maxn]; int Search(int num,int low,int high){ int mid; while(low<=high){ mid=(low+high)/2; if(num>b[mid]) low=mid+1; else high=mid-1; } return low; } void DP(int n,int* x) { int i,len,pos; b[1]=a[1];x[1]=1; len=1; for(i=2;i<=n;i++) { if(a[i]>b[len])//如果a[i]比b[]数组中最大还大直接插入到后面即可 { len=len+1; b[len]=a[i]; pos=len; } else//用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置 { pos=Search(a[i],1,len); b[pos]=a[i]; } x[i]=pos; } } int main(){ int n; while(~scanf("%d",&n)){ int ans=0; for(int i=1;i<=n;++i) scanf("%d",&a[i]); DP(n,c); for(int i=1;i<=n/2;++i) swap(a[i],a[n-i+1]); DP(n,d); for(int i=1;i<=n;++i) if(c[i]==d[n-i+1])ans=max(ans,c[i]+d[n-i+1]-1); else ans=max(ans,min(c[i],d[n-i+1])*2-1); printf("%d\n",ans); } return 0; }