AcWing 1017. 怪盗基德的滑翔翼
原题链接
简单
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, a[5005], dp[5005], k;
void solve(){
for (int i = 1; i <= n; i++){
dp[i] = 1;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= i - 1; j++){
if (a[j] < a[i]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
}
int main(){
cin >> k;
while(k--){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
solve();
int ans = 0, res = 0;
for (int i = 1; i <= n; i++){
ans = max(ans, dp[i]);
}
reverse(a + 1, a + n + 1);
solve();
for (int i = 1; i <= n; i++){
res = max(res, dp[i]);
}
cout << max(res, ans) << endl;
}
return 0;
}