$\LARGE\color{orange}{刷题日记(算法提高课)}$

假设下降方向向左，从任意位置下降当中的最长距离等价于从左往右的最长上升子序列，即从左往右求一遍 LIS
假设下降方向向右，同理可以等价于从右往左求一遍 LIS

这道题就是求两遍 LIS ，然后取二者的最大值

完整代码：

#include <iostream>
#include <cstring>

using namespace std;

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

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

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

        memset(q, sizeof q, 0);
        int len2 = 0;
        q[0] = -1e9;
        for(int i = n; i >= 1; i--)
        {
            int l = 0, r = len2;
            while(l < r)
            {
                int mid = l + r  + 1 >> 1;
                if(q[mid] < a[i]) l = mid;
                else r = mid - 1;
            }
            q[l + 1] = a[i];
            len2 = max(len2, l + 1);
        }
        cout << max(len1, len2) << endl;
    }
    return 0;
}