思路：这题的感觉就是最长上升子序列的升级版。首先对于最长上升子序列要用n*log(n)的算法才行，这个复杂度的算法可以从hdu1025得到启发。然后就是什么情况下最优问题了。对于序列中某个数i，找出其后面最长不下降子序列长度和最长不上升子序列长度，将这两个长度加起来，最大的就是我们要找到。但由于存在相同值，那么我么就要确定这两个子序列中值为i的个数最少的那个，用上面求得和减去它。
我的代码比较挫。
#include<iostream>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdio>
using namespace std;
int ans[],list[],low[],more[],same[];
int main()
{
int t,n,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(low,,sizeof(low));
memset(more,,sizeof(more));
memset(same,,sizeof(same));
for(i=;i<=n;i++)
scanf("%d",&list[i]);
int len;
ans[]=list[n];
low[n]=;
len=;
same[n]=;
int l,r,mid;
for(i=n-;i>=;i--)
{
if(ans[len]>=list[i])
{
ans[++len]=list[i];
low[i]=len;
}
else
{
l=;
r=len;
while(l<=r)
{
mid=(l+r)>>;
if(ans[mid]>=list[i])
l=mid+;
else
r=mid-;
}
ans[l]=list[i];
low[i]=l;
}
l=,r=len;
while(l<=r)
{
mid=(l+r)>>;
if(ans[mid]>list[i])
l=mid+;
else
r=mid-;
}
same[i]=low[i]-r;
}
ans[]=list[n];
len=;
more[n]=;
for(i=n-;i>=;i--)
{
if(ans[len]<=list[i])
{
ans[++len]=list[i];
more[i]=len;
}
else
{
l=;
r=len;
while(l<=r)
{
mid=(l+r)>>;
if(ans[mid]<=list[i])
l=mid+;
else
r=mid-;
}
ans[l]=list[i];
more[i]=l;
}
l=,r=len;
while(l<=r)
{
mid=(l+r)>>;
if(ans[mid]<list[i])
l=mid+;
else
r=mid-;
}
same[i]=min(more[i]-r,same[i]);
}
int Ans=;
for(i=;i<=n;i++)
Ans=max(Ans,low[i]+more[i]-same[i]);
printf("%d\n",Ans);
}
return ;
}