$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

LIS 思路：

• $1. 状态表示$
  $集合：所有以\ h_i\ 为结尾的严格上升子序列$
  $属性：\max$

• $2. 状态转移$
  $f_i=\max \{ f_j+1\}(j<i,h_j<h_i)$

本题思路： $正向和反向各求解一遍\ LIS\ 问题，取\ f_i\ 的最大值$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
int h[N];
int f[N]; //以 h[i] 为结尾的最长严格上升子序列

int main()
{
    int T;
    cin>>T;

    while(T--)
    {
        cin>>n;

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

        //正向求解 LIS 问题
        int res=0;
        for(int i=1;i<=n;i++)
        {
            f[i]=1;
            for(int j=1;j<i;j++)
                if(h[j]<h[i])
                    f[i]=max(f[i],f[j]+1);

            res=max(res,f[i]);
        }

        //反向求解 LIS 问题
        for(int i=n;i;i--)
        {
            f[i]=1;
            for(int j=n;j>i;j--)
                if(h[j]<h[i])
                    f[i]=max(f[i],f[j]+1);

            res=max(res,f[i]);
        }

        cout<<res<<endl;
    }

    return 0;
}