A序列
描述 如果一个序列有奇数个正整数组成，不妨令此序列为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
根据题目要求，在某个数的左边是严格递增，右边是严格递减，所以求出每个数在单调递增／递减序列中的下标，再求出复合题目要求的值，这个值是单调递增和递减所满足的最大值
以题目为例(标示下标) 1 2 5 4 3 6 7 8 9 递增 ( 从左到右递增 ) 1 2 3 3 3 4 5 6 7 递减 ( 从右到左递增 ) 1 1 3 2 1 1 1 1 1
l[i]:代表到达第i个值时的最长子序列是多大 k：表示符合条件的最大子序列的对称点
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <map> #include <stack> #include <cmath> #include <vector> using namespace std; typedef long long ll; const int N=5e5+7; int a[N],b[N]; int l[N],r[N]; int main() { int n; while(~scanf("%d",&n)) { for(int i=0;i<n;i++) { scanf("%d",&a[i]); r[n-1-i]=a[i];//将数组逆向存储，便于找单调递减 } int le=0; b[0]=a[0]; l[0]=le+1; for(int i=1;i<n;i++) { if(a[i]>b[le]) { b[++le]=a[i]; l[i]=le+1; } else { int k=(int)(lower_bound(b,b+le,a[i])-b);//找出大于小于此数的第一个数，并且取代它 b[k]=a[i]; l[i]=k+1; } } int pos=min(1,l[n-1]); le=0; b[0]=r[0]; for(int i=1;i<n;i++) { if(r[i]>b[le]) { b[++le]=r[i]; pos=max(pos,min(le+1,l[n-1-i])); } else { int k=(int)(lower_bound(b,b+le,r[i])-b); b[k]=r[i]; pos=max(pos,min(k+1,l[n-1-i])); } } printf("%d\n",2*pos-1); } }