鏈接：https://vjudge.net/problem/UVA-10534
思路：這可以轉(zhuǎn)換為一個最長上升子序列的問題笤闯，一開始我先枚舉的終點再算懈词，復(fù)雜度是o(n^2logn)蜻势，后來發(fā)現(xiàn)子序列的值算一遍就可以了，可以先算然后再枚舉，復(fù)雜度就是o(nlogn)了粱哼，注意這個題因為上升子序列終點和下降子序列的起點必須是相同的，所以不用記錄用一個ans去記錄最長子序列的最大值檩咱，直接枚舉終點（起點）即可揭措，也不用判斷子序列長度是否相等，直接取最小的那一個拿去更新最大值即可刻蚯，因為大的那一個可以扔掉一些元素標(biāo)為小的那個的長度绊含。
代碼：
#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;
}
