题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4604
思路：这里我是以第一个放入的数为切入点，你要想这个数是一个分水岭，在它之前数都不比它大，之后的数都不比它小。那么在原数列中，那些“之前”的数就应该是它后面的一个非递增序列，那些“之后”的数则是非递减序列。这样，很容易就想到了LIS。当然最朴素的算法是n^2的，想想都知道超时了，所以这里采用二分的方法做，复杂度只有logn。这里的每一个点都要假设一次它是第一个点，从前往后找是不可能的，这里应从后往前找，就只要整体做一遍就可以，这里我选择的是把数组从后往前倒序输入，这样找的时候就可以根据下标顺序找了。当然，在找到的非递增序列和非递减序列中可能有重复的数字，对于第一个放进去的数a，只要两个序列的数字个数和减去a出现次数较少的序列中它的个数就可以了，这里查找这个个数是也要二分，否则会超时。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[100005],t,n;
int s1[100005],s2[100004],num1,num2;
int c1,c2,ans,f1,f2,m1,m2;
int low,high,mid;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=n;i>0;i--)
{
scanf("%d",&a[i]);
}
num1=num2=1;
s1[1]=a[1];
s2[1]=a[1];
ans=1;
for(int i=2;i<=n;i++)
{
if(a[i]>=s1[num1]){s1[++num1]=a[i];c1=num1;}
else
{
low=1;high=num1;
while(low<=high)
{
mid=(low+high)/2;
if(a[i]>=s1[mid])low=mid+1;
else high=mid-1;
}
s1[low]=a[i];
c1=low;
}
if(a[i]<=s2[num2]){s2[++num2]=a[i];c2=num2;}
else
{
low=1;high=num2;
while(low<=high)
{
mid=(low+high)/2;
if(a[i]<=s2[mid])low=mid+1;
else high=mid-1;
}
s2[low]=a[i];
c2=low;
}
low=1;high=c1;
while(low<=high)
{
mid=(low+high)/2;
if(a[i]==s1[mid])high=mid-1;
else low=mid+1;
}
//cout<<high<<" ";
f1=c1-high;
low=1;high=c2;
while(low<=high)
{
mid=(low+high)/2;
if(a[i]==s2[mid])high=mid-1;
else low=mid+1;
}
//cout<<high<<endl;
f2=c2-high;
if(c1+c2-min(f1,f2)>ans)ans=c1+c2-min(f1,f2);
}
cout<<ans<<endl;
}
return 0;
}