9.6腾讯笔试第一题：山谷序列

#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;
}