• 输入

3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

• 输出

6
6
9

代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 110;
int dp[N],w[N],t,n;

//最长上升/下降 子序列
int main(){
    cin >> t;
    while(t--){
        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[i] > w[j])
                    dp[i] = max(dp[i],dp[j] + 1);

            ans = max(ans,dp[i]);
        }

        for(int i=n;i>=1;--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]);
        }
        cout << ans << endl;
    }
    return 0;
}