链接

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,a[1010],dp[1010],cnt,ans,maxn=-1;
int f(int x)
{
	cnt=ans=0;
	memset(dp,0,sizeof(dp));
	dp[0]=-1;
	for(int i=1;i<=x;i++)
	{
		if(a[i]>dp[cnt])dp[++cnt]=a[i];
		else dp[lower_bound(dp+1,dp+1+cnt,a[i])-dp]=a[i];
	}
	ans=cnt;
	cnt=0;
	memset(dp,0,sizeof(dp));
	dp[0]=a[x];
	for(int i=x+1;i<=n;i++)
	{
		if(a[i]<dp[cnt])dp[++cnt]=a[i];
		else dp[lower_bound(dp+1,dp+1+cnt,a[i],greater<int>())-dp]=a[i];
	}
//	cout<<ans<<" "<<cnt<<endl;
	return cnt+ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	 scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		maxn=max(maxn,f(i));
	}
	printf("%d",maxn);
	return 0;
}