// hs 个人见解，有错指出 
#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int a[N], b[N];
int len = 0;

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	/*
	我们需要维护一个 b 数组
	其中 b[i] 代表当前上升子序列长度为 i 时可能的最小数值（注意不是下标）
	定义 len 为当前 LIS（最长上升子序列） 的长度 
	按顺序遍历 a 数组时，如果 a[i] > b[len]
	说明 a[i] 可以直接接在现有的 LIS 后面
	
	反则 a[i] 替换 b 数组中第一个大于（或等于）它的数
	
	有人会问了：判断条件时不是只用到 b[len] 吗
	为什么还要更新 b 数组里别的数？ 
	
	如果每次 a[i] <= b[len] 时都只用 a[i] 更新 b[len] 
	那怎么保证 a[i] > b[len - 1] 呢？
	由此可得，要维护整个 b 数组的递增关系
	
	综上，一个贪心加二分，时间复杂度 O(nlogn)，相当不错 
	*/
	
	len = 0; b[len] = 0;
	for (int i = 1; i <= n; i ++) {
		if (a[i] > b[len]) {
			len ++;
			b[len] = a[i];
		}
		else {
			*lower_bound(b + 1, b + len + 1, a[i]) = a[i];
		}
	}
	
	cout << len << "\n";
	
	return 0;
}

E04 线性DP 最长上升子序列 二分优化

// 二分+贪心 O(nlogn)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+5;
int n, a[N];
int len, b[N]; // 记录上升子序列

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    b[0] = -2e9; // 哨兵
    for (int i = 1; i <= n; i++)
        if (b[len] < a[i])
            b[++len] = a[i]; // a[i]大于队尾数，则插入队尾
        else
            *lower_bound(b + 1, b + len + 1, a[i]) = a[i]; // 用a[i]替换第一个大于等于它的数

    printf("%d\n", len);
    return 0;
}

E03 线性DP 最长上升子序列

状态设计： int f[210000];//f[i]表示只考虑a[1]~a[i]，且一定包含a[i]的最长上升子序列的长度。

状态推导： a[i]问前面的aj： 如果a[i]<=a[j]，则忽略； 如果a[i]>a[j]，那么f[j]+1可以作为f[i]的参考值。 轮到a[i]的时候，前面的f[j]已经填好(1<=j<i）， a[i]对着前面a[j]说：所有比我小的同学，拉着你们原来当最大值时的最长上升子序列加入我的队伍， 并且成为我队伍中第二高的人，我们有机会一起自造最长上升子序列。

// 线性DP O(n^2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10;
int n, a[N], f[N]; // f[i]表示以 a[i] 结尾的最长上升子序列的长度

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);

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