解题思路

左边上升
右边下降
取最大

代码

#include <iostream>

using namespace std;

const int N = 110;
int a[N], f[N];
int n;

int main() {
    int K;
    cin >> K;
    while (K--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];

        int res = 0;
        // 最长上升
        for (int i = 1; i <= n; i++) {
            f[i] = 1;
            for (int j = 1; j < i; j++) {
                if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
            }
            res = max(res, f[i]);
        }
        // 最长下降
        for (int i = 1; i <= n; i++) {
            f[i] = 1;
            for (int j = 1; j < i; j++) {
                if (a[j] > a[i]) f[i] = max(f[i], f[j] + 1);
            }
            res = max(res, f[i]);
        }

        cout << res << endl;
    }
    return 0;
}