#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

typedef int ll;

const int N = 100010;
ll a[N], dp[N];
ll n;
ll len = 1;

int search(ll l, ll r, ll k) {
	ll mid = 0;
	while (l <= r) {
		mid = (l + r) / 2;
		if (dp[mid] >= k) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return l;
}

int main() {
	cin >> n;

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

	dp[1] = a[1];

	for (ll i = 2; i <= n; i++) {
		if (a[i] > dp[len]) {
			dp[++len] = a[i];
		} else {
			dp[search(1, len, a[i])] = a[i];
		}
	}
	
	printf("%d\n", len);
	/*
	8
	1 10 4 5 3 12 6 3
	*/
	return 0;
}

LIS 最长上升子序列

动态规划本质

Future never has to do with past time ,but present does. 现在决定未来，未来与过去无关。

注意本题中的LIS是严格单增（不能重复）

朴素做法 $O(n^2)$

对于每一个元素来说，最长上升子序列就是其本身。
那我们就可以定义一个dp数组 状态设计为，$dp[i]$ 表示以第i元素为结尾的最长上升子序列长度。

至于转移过程，我们可以对于每一个$i$，枚举在$i$之前的每一个元素$j$，然后对于每一个$dp[j]$,如果元素$i$大于元素$j$，那么就可以考虑继承，而最优解的得出则是依靠对于每一个继承而来的dp值，取$max$。

#include<bits/stdc++.h>
const int MAXN=1e5+7;
using namespace std;
int n,a[MAXN], d[MAXN];
int dp() {
	d[1] = 1;
	int ans = 1;
	for (int i = 2; i <= n; i++) {
		d[i] = 1;
		for (int j = 1; j < i; j++)
			if (a[j] < a[i]) {
				d[i] = max(d[i], d[j] + 1);
				ans = max(ans, d[i]);
			}
	}
	return ans;
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	cout<<dp()<<'\n';
	return 0;
}

优化做法 $O(nlogn)$

不难看出，对于$O(n^2)$做法而言，其实就是暴力枚举。 那可不可以优化呢?

显然是可以的
我们将原来的dp数组的存储由数值换成该序列中，上升子序列长度为$i$的上升子序列的最小末尾数值。

这个方法极其贪心，但是如果你仔细想，你会发现，他是正确的。

关键操作是每遇到一个新的元素时，就跟已经记录的dp数组当前所记录的最长上升子序列的末尾元素相比较：如果小于此元素，那么就不断向前找，直到找到一个刚好比它大的元素，替换；反之如果大于，么填到末尾元素的下一个。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+7;
int n,a[N],f[N];
signed main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        f[i]=0x7f7f7f7f;
    }
    f[1]=a[1];
    int len=1;
    for(int i=2; i<=n; i++)
        if(a[i]>f[len])f[++len]=a[i];
        else {
            int pos=lower_bound(f+1,f+len+1,a[i])-f;
            f[pos]=min(a[i],f[pos]);
        }
    cout<<len<<'\n';
    return 0;
}