题目描述

最长上升子序列解题报告
给定一个长度为N的数列(w[N])，求数值严格单调递增的子序列的长度最长是多少。

样例
输入格式
第一行包含整数N。

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

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

数据范围
1 ≤ N ≤ 1000，
−1e9 ≤ 数列中的数 ≤ 1e9

样例

输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

算法1

(DP) $O(n^2)$

• 状态表示： f[i]表示的集合是所有从第一个数开始算，以第 i个数结尾的上升子序列。属性是所有集合中序列长度最大值
• 状态计算： f[i] = max(f[j]) + 1, j ∈ 0,1,2...i-1
• 答案： max(f[i]), i ∈ 0,1,2...n

时间复杂度

补充一句：DP的时间复杂度计算=状态的数量*每个状态的计算量
本题目中状态数量 n，每个状态 f[i]计算量 n，所以总体时间复杂度 $O(n^2)$

C++ 代码

#include<iostream>
using namespace std;

const int N = 1010;
int a[N], f[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[j]+1, f[i]);
            }
        }
    }

    int ret = 0;
    for(int i = 1; i <= n; i++){
        ret = max(ret, f[i]);
    }
    cout << ret << endl;
    return 0;
}