对于a[i]，当确定了方向后，就变成了LIS问题，向左飞就是以a[i]为终点的LIS，向右飞就是逆序的以a[i]为终点的LIS。
所以正逆做两次LIS，就能找出答案了。

动态规划解决LIS

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

        int res = 0;
        for (int i = 1; i <= n; i ++ ) {
            f[i] = 1;
            for (int j = 0; j < i; j ++ ) {
                if (a[i] > a[j]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            res = max(res, f[i]);
        }

        for (int i = n; i > 0; i -- ) {
            f[i] = 1;
            for (int j = n; j > i; j -- ) {
                if (a[i] > a[j]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            res = max(res, f[i]);
        }

        printf("%d\n", res);
    }

    return 0;
}

贪心做LIS版

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

        int res = 0;

        q[0] = -1;
        int len = 0;
        for (int i = 1; i <= n; i ++ ) {
            int l = 0, r = len;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (q[mid] < a[i]) l = mid;
                else r = mid - 1;
            }
            len = max(len, l + 1);
            q[l + 1] = a[i];
        }
        res = max(res, len);

        len = 0;
        for (int i = n; i; i -- ) {
            int l = 0, r = len;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (q[mid] < a[i]) l = mid;
                else r = mid - 1;
            }
            len = max(len, l + 1);
            q[l + 1] = a[i];
        }
        res = max(res, len);

        printf("%d\n", res);
    }

    return 0;
}