发布时间: 2017年7月9日 20:20 最后更新: 2017年7月10日 21:11 时间限制: 1000ms 内存限制: 128M
描述如果一个序列有奇数个正整数组成，不妨令此序列为 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 选择语言 想法： 先找出递增序例 反过来找递减序例 再取所有值（取两者最小值）中最大值，再乘2减1 穷举会超时，使用lower_bound函数找 代码： #include<bits/stdc++.h> using namespace std; const int maxn= 50005; const int INF = 0x3f3f3f3f; int num[maxn]; int temp[maxn]; int l[maxn]; int r[maxn]; int main() { int n; while(~scanf("%d",&n)) { for(int i=1; i<=n; i++) { scanf("%d",&num[i]); } int Max=1; memset(temp,0x3f,sizeof(temp)); temp[0]=-1; for(int i=1; i<=n; i++) //求最长单调递增子序列 { int pos=lower_bound(temp,temp+n,num[i])-temp; temp[pos]=num[i]; Max=max(Max,pos); l[i]=Max; } Max=1; memset(temp,0x3f,sizeof(temp)); temp[0]=-1; for(int i=n; i>=1; i--) //求单调递减子序列 { int pos=lower_bound(temp,temp+n,num[i])-temp; temp[pos]=num[i]; Max=max(Max,pos); r[i]=Max; } int ans=1; for(int i=1;i<=n;i++) { ans=max(ans,min(l[i],r[i])); } printf("%d\n",ans*2-1); } return 0; }