Uva(10534)(waviosequence)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n;
int a[10001],b[10001];
int f1[10001],f2[10001],g1[10001],g2[10001];

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(~scanf("%d",&n)){
        for(int i=0;i<n;++i){
            scanf("%d",&a[i]);
            b[n-i-1] = a[i];//反向就变成最长上升子序列了
        }
        int res = 0;
        memset(f1,0,sizeof(f1));
    memset(f2,0,sizeof(f2));
       for(int m=1;m<=n;m++){
            g1[m] = 1e9;
            g2[m] = 1e9;
        }
//算出正反的最长上升子序列
for(int j=0;j<n;j++){
    int k1 = lower_bound(g1+1,g1+1+n,a[j])-g1;
    f1[j] = k1;
    g1[k1] = a[j];
}
for(int k=0;k<n;k++){
    int k2 = lower_bound(g2+1,g2+1+n,b[k])-g2;
    f2[k] = k2;
    g2[k2] = b[k];
}
//枚举终点(起点)并更新最大值
for(int i=0;i<n;i++){
    res = max(res,min(f1[i],f2[n-i-1]));
}
        printf("%d\n",2*res-1);
    }
    return 0;
}