1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1010;
6

7
int n;
8
int w[N], f[N];
9

10
int main()
11
{
12
    cin >> n;
13
    for (int i = 1; i <= n; i ++ )  cin >> w[i];
14

15
    for (int i = 1; i <= n; i ++ )
16
    {
17
        f[i] = 1;
18
        for (int j = 1; j < i; j ++ )
19
            if (w[i] > w[j])
20
                f[i] = max(f[j] + 1, f[i]);
21
    }
22

23
    int res = -1;
24
    for (int i = 1;i <= n; i ++ )
25
        res = max(res, f[i]);
26

27
    cout << res << endl;
28

29
    return 0;
30
}

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1e5 + 10;
6

7
int a[N], q[N];
8
int n;
9

10
int main()
11
{
12
    cin >> n;
13
    for (int i = 0; i < n; i ++ )  cin >> a[i];
14

15
    int len = 0;
16
    q[0] = -2e9;
17
    for (int i = 0; i < n; i ++ )
18
    {
19
        int l = 0, r = len;
20
        while (l < r)
21
        {
22
            int mid = l + r + 1 >> 1;
23
            if (q[mid] < a[i])  l = mid;
24
            else r = mid - 1;
25
        }
26
        len = max(len, r + 1);
27
        q[r + 1] = a[i];
28
    }
29

30
    cout << len << endl;
31
    return 0;
32
}