AcWing 1017. 怪盗基德的滑翔翼
原题链接
简单
作者:
yi生守护你
,
2022-05-10 13:27:51
,
所有人可见
,
阅读 87
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int w[N], dp[N];
int main()
{
int T;
scanf("%d", &T);
while (T --)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
int ans = 0;
for (int i = 1; i <= n; i++)
{
dp[i] = 1;
for (int j = 1; j < i; j++)
if (w[j] < w[i])
dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
for (int i = n; i ; i--)
{
dp[i] = 1;
for (int j = n; j > i; j--)
if(w[i] > w[j])
dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
}
return 0;
}