最长上升子序列

题目描述

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

输入格式

第一行包含整数N。

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

输出格式

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

数据范围

1≤N≤1000，
−109≤数列中的数≤109

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N];//f[i]表示所有以a[i]结尾的严格单调上升的子序列的最大长度
//f[i]划分标准：
//以倒数第二个数来划分:  不存在(为空,序列只有a[i]自己)、a[1]、a[2]、a[3]···a[i - 1].

int main(){
    cin >> n;

    for(int i = 1; i <= n; i ++) cin >> a[i];

    for(int i = 1; i <= n; i ++){
        f[i] = 1;//倒数第二个元素不存在,即序列中只有a[i]自己,因此长度为1
        for(int j = 1; j < n; j ++){//倒数第二个数为a[k]
            if(a[j] < a[i]){//虽然划分包含所有a[i],但其不一定合法，因此需要提前预判一下
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }

    int maxv = -1;
    for(int i = 1; i <= n; i ++) maxv = max(maxv, f[i]);

    cout << maxv << endl;

    return 0;
}