题目描述

一个数的序列，当的时候，我们称这个序列是上升的。对于给定的一个序列，我们可以得到一些上升的子序列，这里。比如，对于序列，有它的一些上升子序列，如等等。这些子序列中最长的长度是 ，比如子序列。

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入

输入的第一行是序列的长度 。第二行给出序列中的N个整数，这些整数的取值范围都在 到 。

输出

最长上升子序列的长度。

样例

输入样例

7
1 7 3 5 9 4 8

输出样例

4

源代码

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int a[1001], f[1001];
int main() {
    int i, j, n, maxx = 0;
    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i];
    for (i = 1; i <= n; i++) {
        f[i] = 1;
        for (j = 1; j < i; j++)
            if (a[j] < a[i]) f[i] = max(f[j] + 1, f[i]);
        maxx = max(maxx, f[i]);
    }
    cout << maxx;
    return 0;
}