[AcWing] 1014. 登山（C++实现）最长上升子序列模型、求正反向最长上升子序列之和

[AcWing] 1014. 登山（C++实现）最长上升子序列模型、求正反向最长上升子序列之和

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

1. 题目

2. 读题（需要重点注意的东西）

读题：
① 每次所浏览景点的编号都要大于前一个浏览景点的编号 ===》 单调
② 一旦开始下山，就不再向上走了 ===》 可以反向
③ 尽可能多的浏览景点 ===》 最长

单调 + 最长 ===》 最长上升子序列模型

最长上升子序列模型 + 可以反向 ===》 [AcWing] 1017. 怪盗基德的滑翔翼（C++实现）最长上升子序列模型

思路：
最长上升子序列模型 + 可以反向 ===》 [AcWing] 1017. 怪盗基德的滑翔翼（C++实现）最长上升子序列模型
本题取的最大值是正向和反向之和的最大值，这是与题目1017唯一不同的地方！

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include
#include
using namespace std;

const int N = 1010;
int n;
int h[N];
int f[N];
int g[N];


int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%d",&h[i]);
    
    // 正向
    for(int i = 1;i <= n;i++){
        f[i] = 1;
        for(int j = 1;j <= n;j++)
            if(h[j] < h[i]) f[i] = max(f[i],f[j]+1);
    }
    
    // 反向
    for(int i = n;i >= 1;i--){
        g[i] = 1;
        for(int j = n;j >= i;j--)
            if(h[j] < h[i]) g[i] = max(g[i],g[j]+1);
    }
    
    // 求最大值
    int res = 0;
    
    for(int i = 1;i <= n;i++) res = max(res,f[i]+g[i]-1);
    
    cout << res;
    
    return 0;
}

---

可能存在的问题

4. 可能有帮助的前置习题

• [AcWing] 897. 最长公共子序列（C++实现）线性dp例题

5. 所用到的数据结构与算法思想

• 动态规划
• 最长上升子序列问题

6. 总结

最长上升子序列模型，可以发展为不同的最长上升子序列题目

最长上升子序列模型的特征：
1. 以每个点为终点都要判断一遍
2. 路径为一条上升子序列（或下降子序列）