板子题，两次LIS（一次升一次降）

以下是完全正确的AC代码【PS：记住为什么第二套代码不能AC的原因，防止以后出错】

/*
 * @Author: YMYS
 * @Date: 2024-12-17 08:44:40
 * @LastEditTime: 2024-12-18 18:15:02
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法提高课\1.动态规划\2.最长上升子序列模型\1.怪盗基德的滑翔翼.cpp
 * @URL:https://www.acwing.com/problem/content/1019/
 * @Description: 1017. 怪盗基德的滑翔翼
 * 思路：
 * 这道题本质其实就是弄两次“最长上升子序列（LIS）”模型，
 * 一次正向一次反向，
 * 注意代码细节即可
 */
#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int T;
int n,w[N], dp[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];

    //《《正向与反向LIS的本质区别》》
    //dp[i]：表示以w[i]结尾的最长上升子序列的长度的数值
    //正向是从1~n遍历，也就是让w[1]做头部，w[n]做尾部
    //而反向是从n~1遍历，也就是让w[n]做头部，w[1]做尾部
    //也可以这么说：就是一个在求最长上升子序列一个在求最长下降子序列

    //res用于找出最大的dp[]的值
    int res = 1;

    //开始正向的LIS
    for(int i=1;i<=n;i++){
        dp[i] = 1;
        for(int j=1;j<i;j++){//1~n-1
            if(w[i]>w[j]){
                dp[i] = max(dp[i], dp[j]+1);
            }
        }

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

    //反向LIS
    for(int i=n;i>=1;i--){
        dp[i] = 1;
        for(int j=n;j>i;j--){//n~i+1
            if(w[i]>w[j]){
                dp[i] = max(dp[i], dp[j]+1);
            }
        }

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

    cout<<res<<endl;

    return;
}

int main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

以下代码是不能ac的，原因是在两次LIS遍历中，res并没有正确留存max
我们想要正确遍历两次LIS的dp[]数组，必须也得让res遍历两次

/*
 * @Author: YMYS
 * @Date: 2024-12-17 08:44:40
 * @LastEditTime: 2024-12-18 18:09:36
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法提高课\1.动态规划\2.最长上升子序列模型\1.怪盗基德的滑翔翼.cpp
 * @URL:https://www.acwing.com/problem/content/1019/
 * @Description: 1017. 怪盗基德的滑翔翼
 * 思路：
 * 这道题本质其实就是弄两次“最长上升子序列（LIS）”模型，
 * 一次正向一次反向，
 * 注意代码细节即可
 */
#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int T;
int n,w[N], dp[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];

    //《《正向与反向LIS的本质区别》》
    //dp[i]：表示以w[i]结尾的最长上升子序列的长度的数值
    //正向是从1~n遍历，也就是让w[1]做头部，w[n]做尾部
    //而反向是从n~1遍历，也就是让w[n]做头部，w[1]做尾部
    //也可以这么说：就是一个在求最长上升子序列一个在求最长下降子序列

    //开始正向的LIS
    for(int i=1;i<=n;i++){
        dp[i] = 1;
        for(int j=1;j<i;j++){//1~n-1
            if(w[i]>w[j]){
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
    }

    //反向LIS
    for(int i=n;i>=1;i--){
        // dp[i] = 1;
        for(int j=n;j>i;j--){//n~i+1
            if(w[i]>w[j]){
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
    }  

    //找出最大的dp[]的值
    int res = 1;
    for(int i=1;i<=n;i++){
        res = max(res, dp[i]);
    }

    cout<<res<<endl;

    return;
}

int main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}