Uva(10534)(waviosequence)

链接：https://vjudge.net/problem/UVA-10534
思路：这可以转换为一个最长上升子序列的问题，一开始我先枚举的终点再算，复杂度是o(n^2logn)，后来发现子序列的值算一遍就可以了，可以先算然后再枚举，复杂度就是o(nlogn)了，注意这个题因为上升子序列终点和下降子序列的起点必须是相同的，所以不用记录用一个ans去记录最长子序列的最大值，直接枚举终点（起点）即可，也不用判断子序列长度是否相等，直接取最小的那一个拿去更新最大值即可，因为大的那一个可以扔掉一些元素标为小的那个的长度。
代码：

#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;
}