题目传送门
思路：求A序列（先是单调递增然后单调递减），相当于求当前位置的最长递增子序列和反方向的最长递增子序列，取其中小的乘以2减1就是最长的A序列。就是求两次LIS问题，然后遍历找最大A序列。
下面是代码：
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<stack> #include<algorithm> using namespace std; int num[500005],n,k; int dp[2][500005],ans; int x[500005]; int main() { while(~scanf("%d",&n)) { int k=0,ans=0,flag=1; for(int i=0;i<n;i++) { scanf("%d",&num[i]); } x[1]=num[0]; k=1; dp[0][0]=1; for(int i=1;i<n;i++) { if(x[k]<num[i]) { x[++k]=num[i]; dp[0][i]=k; } else { for(int j=1;j<=k;j++) { if(x[j]>=num[i]) { dp[0][i]=j; x[j]=num[i]; break; } } } //cout<<dp[0][i]<<' '; } //cout<<endl; x[1]=num[n-1]; k=1; dp[1][n-1]=1; for(int i=n-2;i>=0;i--) { if(x[k]<num[i]) { x[++k]=num[i]; dp[1][i]=k; } else { for(int j=1;j<=k;j++) { if(x[j]>=num[i]) { dp[1][i]=j; x[j]=num[i]; break; } } } //cout<<dp[1][i]<<' '; } //cout<<endl; ans=0; for(int i=0;i<n;i++) ans=max(ans,min(dp[0][i],dp[1][i])); printf("%d\n",ans*2-1); } }