AcWing 1017. 怪盗基德的滑翔翼
原题链接
简单
作者:
_empty
,
2019-09-25 08:20:34
,
所有人可见
,
阅读 1070
/*
LIS 问题派生问题
时间复杂度:O(n^2)
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e2+10;
int n,a[N],f[N],d[N];
int main()
{
int k;
cin>>k;
while(k--)
{
cin>>n;
int ans1=0,ans2=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
f[i]=d[i]=1;
for(int j=1;j<=i;j++)
if(a[i]<a[j])
f[i]=max(f[i],f[j]+1);
else if(a[i]>a[j])
d[i]=max(d[i],d[j]+1);
ans2=max(ans2,d[i]);
ans1=max(ans1,f[i]);
}
cout<<max(ans1,ans2)<<endl;
}
return 0;
}