AcWing 1017. 怪盗基德的滑翔翼
原题链接
简单
作者:
pleviumtan
,
2019-10-01 23:32:55
,
所有人可见
,
阅读 668
单减子序列换个方向就是单增子序列
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int f[N],g[N],a[N];
int k;
int main()
{
scanf("%d",&k);
while(k--)
{
int n;
scanf("%d",&n);
for (int i = 1; i <= n; i++)
scanf("%d",&a[i]);
for(int i = 1; i<= n ; i++)
{
f[i] = 1;
g[i] = 1;
for(int j = 1; j < i ; j++)
{
if(a[j]>a[i])
f[i] = max(f[i],f[j]+1);
if(a[j]<a[i])
g[i] = max(g[i],g[j]+1);
}
}
int res = 0;
for(int i = 1; i <= n; i++)
{
if(f[i]>res)res = f[i];
if(g[i]>res)res = g[i];
}
printf("%d\n",res);
}
return 0;
}