按照题目要求，由于可以从任意顶端开始，其实就是求LIS（最长上升子序列）和LDS（最长下降子序列）
这里用一次dp循环直接计算两个最值。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int f1[N], f2[N], h[N];

int main() {
    int k;
    cin >> k;
    while(k--) {
        memset(f1, 0, sizeof f1);
        memset(f2, 0, sizeof f2);
        memset(h, 0, sizeof h);
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) scanf("%d", &h[i]);

        // 这里边计算边比较，这样就不需要再最后循环获得最大值。
        int res1 = 1, res2 = 1;
        for (int i = 1; i <= n ; i++) {
            f1[i] = 1;
            f2[i] = 1;
            for (int j = 1; j < i; j++) {
                if (h[i] > h[j]){
                    f1[i] = max(f1[i], f1[j] + 1);
                } else if (h[i] < h[j]) {
                    f2[i] = max(f2[i], f2[j] + 1);
                }
            }
            res1 = max(res1, f1[i]);
            res2 = max(res2, f2[i]);
        }

        cout << max(res1, res2) << endl;    // 二选一
    }

    return 0;

}