题目链接

AcWing 895. 最长上升子序列 - AcWing

一些话

切入点

输出一个整数，表示最大长度。

区间长度类的最优解，符合dp特征（maxn）

数据范围

1≤N≤1000

1e3的数据范围，符合dp特征

流程

// 状态表示，用一维f[i]来表示以a[i]为结尾的最大上升子序列长度

            属性是最大值

// 状态计算，找最后一位不同的作为分界点

           最后一位都是a[i],相同，继续往前找

           // a[i-1]，有不同，不是所有情况都包含，开始划分集合：

           a[1] ~ a[i-1]

           a[2] ~ a[i-1]

           a[3] ~ a[i-1]

           …………

           a[i-1] ~ a[i-1]

            空

           在里面找出最大值

            划分出来的这部分集合的最大值就等价于f[i-1]（以a[i-1]为结尾的最大上升子序列），在前一层中可以求到

划分出来的集合

           a[1] ~ a[i-1]

           a[2] ~ a[i-1]

           a[3] ~ a[i-1]

           …………

           a[i-1] ~ a[i-1]

“空”代表的原本是a[i],所有集合减去a[i]后，原本表示a[i]的集合就变成了空

（，按照这样一直到第一层

套路

区间类的最优解dp

{

f[i]集合表示成以a[i]为结尾的区间

集合划分成不同起点到a[i-1],等价于f[i-1]来计算

}

ac代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1100;
int f[N],a[N];
int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++){
        f[i] = 1;
        for(int j = 1;j < i;j++){
            if(a[j] < a[i]){
                f[i] = max(f[i],f[j] + 1);
            }
        }
    }
    int res = 0;
    for(int i = 1;i <= n;i++){
        res = max(f[i],res);
    }
    cout << res << endl;
    return 0;
}