最长上升子序列模型

可以先上升，再下降，也可以一直下降，也可以一直上升。

我们只需要计算以每个点为中间，左边下降，右边也是下降的最大长度。

可以先计算出，从左边开始，对于每个点的最大上升子序列最大值。从右边开始，往左边走的对于每个点的最大上升子序列最大值。

最后遍历每个点，对于每个点作为中间的点，最大的值是 f[i] + g[i] - 1;

$ 时间复杂度O(N^2)，空间复杂度O(N) $

参考文献

算法提高课

AC代码

#include <iostream> 
using namespace std;

const int N = 1e3 + 10;

int n;
int a[N], f[N], g[N];

int main(){
    //读入 
    cin >> n;
    for (int i = 0 ; i < n ; i++) cin >> a[i];

    //从前到后最长上升子序列
    for (int i = 0 ; i < n ; i ++){
        f[i] = 1;
        for (int j = 0 ; j < i ; j ++){
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        }
    }
    //从后往前最长下降子序列
    for (int i = n - 1 ; i >= 0 ; i --){
        g[i] = 1;
        for (int j = n - 1 ; j > i ; j --){
            if (a[j] < a[i]) g[i] = max(g[i], g[j] + 1);
        }
    }
    //求答案
    int res = 0;
    for (int i = 0 ; i < n ; i ++){
        res = max(res, f[i] + g[i] - 1);
    }

    cout << res;

    return 0;

}