最长上升子序列模型 闫氏dp法

最长上升子序列基础题模型 链接 ：最长上升子序列模板题

最长上升子序列基础题题解 链接 ： 最长上升子序列模板题 题解

本题的思路很简单 题目所说的 怪盗基德可以从任一位置开始 也就是 题目所给的顺序并不是严格顺序 可以倒序进行

说到这里了 大家都知道了 可以进行两次取最长上升子序列 求两次的最大值就好了 是不是很简单

不知道怎么求最长上升子序列的同学可以移步上面的链接 基础题解

Code：

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int t;
int a[110] , f[110];
signed main()
{
    ios::sync_with_stdio(false); //取消输入输出流
    cin >> t;
    int ans ;  // 记录答案；；
    while (t --) 
    {
        int  n;
        cin >> n;
        ans = 0; // 每次都要归零 不然会影响一下组 测试点
        for (int i = 1 ; i <= n ; i ++ ) cin >> a[i] ; 
        for (int i = 1 ; i <= n ; i ++ )   //正向最长上升子序列
        {   
            f[i] = 1;       //每个f[i] 都是一个楼 也是最低的答案 1
            for (int j = 1 ; j < i ; j ++ ) 
                if (a[i] > a[j]) f[i] = max(f[i] , f[j] + 1);
            ans = max(ans , f[i]);   //更新答案
        }
        for (int i = n ; i >= 1 ; i -- )  //反向最长上升子序列
        {
            f[i] = 1;   //这里也需要初始值为1
            for (int j = n ; j > i ; j -- )
                if (a[i] > a[j]) f[i] = max(f[i] , f[j] + 1);
            ans = max(ans , f[i]);      //更新答案
        }
        cout << ans << endl;
    }
    return 0;
}