9.6腾讯笔试第一题：山谷序列
100%通过
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
int m;
cin >> m;
vector<int> nums(m);
for(int i = 0; i < m; i++) cin >> nums[i];
//dp[i]是以nums[i]为结尾的最长递减子序列长度
vector<int> dp1(m, 1);
for(int i = 1; i < m; i++){
for(int j = 0; j < i; j++){
if(nums[i] < nums[j]) dp1[i] = max(dp1[j]+1, dp1[i]);
}
}
//dp[i]是以nums[i]为开头的最长递增子序列长度
vector<int> dp2(m, 1);
for(int i = m-2; i >= 0; i--){
for(int j = m-1; j > i; j--){
if(nums[i] < nums[j]) dp2[i] = max(dp2[j]+1, dp2[i]);
}
}
int res = 0;
for(int i = 0; i < m-1; i++){
for(int j = i+1; j < m; j++){
if(nums[i] == nums[j]){
int temp = min(dp1[i], dp2[j]);
res = max(res, temp*2);
}
}
}
cout << res << endl;
}
return 0;
}
