图片加载可能有点慢，请跳过题面先看题解，谢谢
设 \(L[i]\) 为 \(i\) 位置的最长上升子序列的长度
设 \(R[i]\) 为 \(i\) 位置的最长下降子序列的长度 答案为：\(max(min(L[i],R[i])*2-1)\) 这里用到二分栈求 \(LIS\)//made by Hero_of_Someone#include#include #include #include #define il inline#define RG registerusing namespace std;il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar(); if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }int n,cnt,a[10010];int s[10010],L[10010],R[10010];il void init(){ for(int i=1;i<=n;i++) a[i]=gi();}il void work(){ memset(s,0,sizeof(s)); cnt=0; for(RG int i=1;i<=n;i++){ RG int x=a[i]; RG int l=1,r=cnt,k=0; while(l<=r){ RG int mid=(l+r)>>1; if(s[mid]>=x) r=mid-1; else l=mid+1,k=mid; } if(k==cnt) s[++cnt]=x,L[i]=cnt; else s[k]=min(s[++k],x),L[i]=L[i-1]; } memset(s,0,sizeof(s)); cnt=0; for(RG int i=n;i;i--){ RG int x=a[i]; RG int l=1,r=cnt,k=0; while(l<=r){ RG int mid=(l+r)>>1; if(s[mid]>=x) r=mid-1; else l=mid+1,k=mid; } if(k==cnt) s[++cnt]=x,R[i]=cnt; else s[k]=min(s[++k],x),R[i]=R[i+1]; } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,min(L[i],R[i])*2-1); printf("%d\n",ans);}int main(){ while(scanf("%d",&n)!=EOF){ init(); work(); } return 0; }