朴素解法：

f[i] 表示以 i 结尾的最长上升子序列的长度

枚举每一个 i 作为右端点，接着从1 ~ i 枚举 j ，如果符合条件就判断能不能让以 i 结尾的最长上升子序列长度增加

时间复杂度：O（N ^ 2）

代码略

二分优化

f[i] 表示长度为 i 的最长上升子序列末尾的最小元素

贪心思想，每次判断能否加入末尾，如果可以直接加入，不行则在序列中寻找第一个比要加入元素大的值，替换它

时间复杂度：O (n log2 n）

code:

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>

#define endl "\n"
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
#define ULL unsigned long long
#define INF 0x3f
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define mid(a, b) (a + b) >> 1 

const int N = 1e4 + 7, M = 1e3 + 9, P = 131, MOD = 1e6 + 7;

using namespace std;	

inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if(c == '-') flag = true;
    else num = c - '0';
    while(isdigit(c = getchar())) num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
} 

int t;

int n, len;

int a[N], f[N];

void init()

{
	n = read();
	for (int i = 1; i <= n; i ++ ) a[i] = read();
	f[++ len] = a[1];
}

int find(int x)//二分查找 

{
	int l = 1, r = len;
	while (l < r) 
	{
		int mid = mid(l, r);
		if (f[mid] < x) l = mid + 1;
		else r = mid;
	}
	return l;
}

void solve()

{
	init();
	
	for (int i = 2; i <= n; i ++ )
	{
		if (f[len] < a[i]) f[++ len] = a[i];
		else
		{
			int temp = find(a[i]);
			f[temp] = a[i];
		}
	}
	cout << len << endl;
	//puts("");
}

signed main()

{
	IOS;
	
	t = 1;
	//t = read();
	while (t -- ) solve();
}