题目

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。第二行包含 N个整数，表示完整序列。

数据范围

1≤N≤1000，
−10e9≤数列中的数≤10e9

示例

7
3 1 2 1 8 5 6

知识点

  1. 动态规划——状态计算
    如果我们选第 1个数，那么对应的就是 f1
    如果我们选第 2个数，那么对应的就是 f2
    如果我们选第 j个数，那么对应的就是 fj
    所以状态转移方程就是 fi=max1≤j<i{fj+1}
  2. 初始化：因为每一个数以自己结尾的最长上升子序列的长度为 1
    ，所以初始 f[i] = 1

通俗一点的思考就是 找自己之前比自己小的数 在这个小的数的状态上+1 取max

代码

#include <iostream>
using namespace std;

const int N = 1010;
int n;
int a[N],f[N];
int res = 1;

int main()
{
    cin >> n;
    for(int i = 0;i < n;i++) cin >> a[i];
    for(int i = 0;i < n;i++)
    {
        //f[i]默认是1，如果前面找不到比自己小的数字就是1
        f[i] = 1;
        for(int j = 0;j < i;j++)
        {
            if(a[i] > a[j]) f[i] = max(f[i],f[j] + 1);
        }
        res = max(res,f[i]);
    }
    cout << res <<endl;
    return 0;
};