“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛 F.A序列

A序列

发布时间: 2017年7月9日 18:17   最后更新: 2017年7月9日 21:05   时间限制: 1000ms   内存限制: 128M

描述

如果一个序列有奇数个正整数组成，不妨令此序列为a 1 ,a 2 ,a 3 ,...,a 2∗k+1   (0<=k  )，并且a 1 ,a 2 ...a k+1   是一个严格递增的序列，a k+1 ,a k+2 ,...,a 2∗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

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define pb push_back
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define cls(name,x) memset(name,x,sizeof(name))
using namespace std;
const int inf=1e9+10;
const ll llinf=1e16+10;
const int maxn=5e5+10;
const int maxm=1e2+10;
const int mod=1e9+7;
int n;
int dp[maxn];
int ans[2][maxn];
int num[maxn];
int main()
{
    char s[maxn];
    //freopen("in.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        cls(dp,0);
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        int k=1;
        dp[k]=num[1];
        ans[0][1]=1;
        for(int i=2;i<=n;i++)
        {
            if(num[i]>dp[k])
            {
                dp[++k]=num[i];
                ans[0][i]=k;
            }
            else
            {
                int temp=lower_bound(dp+1,dp+k,num[i])-dp;
                dp[temp]=num[i];
                ans[0][i]=temp;
            }
        }

        ans[1][n]=1;
        cls(dp,0);
        k=1;
        dp[k]=num[n];
        for(int i=n-1;i>=1;i--)
        {
            if(num[i]>dp[k])
            {
                dp[++k]=num[i];
                ans[1][i]=k;
            }
            else
            {
                int temp=lower_bound(dp+1,dp+k,num[i])-dp;
                dp[temp]=num[i];
                ans[1][i]=temp;
            }
        }
        int res=0;
        for(int i=1;i<=n;i++)
        {
            //printf("[%d %d]",ans[0][i],ans[1][i]);
            res=max(res,min(ans[0][i],ans[1][i])*2-1);
        }
        printf("%d
",res);
    }
    return 0;
}