简略题意

给你一个数列，里面有$\ n\ $个元素，求解从任意一个数开始的最长上升或下降子序列。

思路

这道题很明显的板子题。

既然要最长，必然从两端开始。因此我们只需要求解从数列中的第一个元素和最后一个元素开始的最长上升子序列，并取最大值即可。

复杂度分析

• 时间复杂度：$O(N ^ 2)$

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int t;
int n;
int a[N];
int f[N];

int main()
{
    cin >> t;
    while(t--)
    {
        for(int i = 1; i <= N; i++)
            f[i] = 1;

        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> a[i];

        for(int i = 1; i <= n; i++)
            for(int j = i - 1; j; j--)
                if(a[j] < a[i])
                    f[i] = max(f[i], f[j] + 1);

        int ans = 0;
        for(int i = 1; i <= n; i++)
            ans = max(ans, f[i]);

        //cout << ans << ' ';
        for(int i = 1; i <= N; i++)     //这里记得清空f就好
            f[i] = 1;

        for(int i = n; i; i--)
            for(int j = i + 1; j <= n; j++)
                if(a[j] < a[i])
                    f[i] = max(f[i], f[j] + 1);

        for(int i = n; i; i--)
            ans = max(ans, f[i]);

        cout << ans << endl;
    }

    return 0;
}