#include <bits/stdc++.h>
using namespace std;

//dp:长度为i的LIS的最后一位最小值是多少
int a[100100],dp[100100];
int i,n,l,r,mid;

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

	//边界
	dp[1] = a[1];
	int len = 1;//LIS的长度
	//从第2个数开始求解
	for(i = 2; i <= n; i++) {
		//如果a[i]比dp最后一位大,a[i]直接续上去,增加LIS的长度
		if(a[i] > dp[len]) {
			len++;
			dp[len] = a[i];
		} else {
			//二分查找到dp数组中第1个>=a[i]的元素下标，替换（dp数组一定是递增的）
			l = 1;
			r = len;
			while(l <= r) {
				mid = (l + r) / 2;
				if(a[i] <= dp[mid]) r = mid - 1;
				else l = mid + 1;
			}

			//替换
			dp[l] = a[i];
		}
	}

	printf("%d",len);
}

这题有点意思。搞出个ac 59ms，也不知道是不是学院派的解法。速度也可能因题而异。如果里面十万个数全都是递增，可能就慢了。这里面longest—head[n]是n个数字长的子序列最大的那个数，也就是最右边那个。读入一个新的数字，比较每一个长度是n-1的子序列头部，如果大于这个数字，而且小于长度是n的子序列的头部，就替换这个长度n的子序列头部。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-')f = -1; ch = getchar();}
    while (isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x * f;
}
int main() {
    int n = read();
    int longest_head[n + 1];
    register int a, longest = 1;
    longest_head[1]  = read();
    longest_head[0] = -2e9;
    for (register int i = 1; i < n; i++) {
        a = read();
        if (longest_head[longest] < a) longest_head[++longest] = a;
        for (register int j = longest; j > 0; j--) {
            if (a > longest_head[j - 1] and a < longest_head[j]) 
                longest_head[j] = a;
        }
    }
    cout << longest;
}

#include <bits/stdc++.h>
using namespace std;
int n,a[100001],ans = 0,dp[100001];                   //dp[i]存储从数组第i位开始的LIS长度
int LIS(int p){
    if (p == n) return 1;                             //最后一个元素开头的LIS长度自然为1
    if (dp[p]) return dp[p];                          //记忆化搜索，减少重复计算，全局变量默认为0，对应bool值是false，赋值后变为true
    int max_len = 1;                                  //若把一个元素理解为一个LIS，那么一个LIS最小长度为1
    for (int i = p + 1;i <= n;i++){
        if (a[i] > a[p]){
            max_len = max(max_len,LIS(i) + 1);        //求长LIS的短子串中的LIS长度，用max()选择保留或更改
        }
    }
    dp[p] = max_len;                                  //储存结果（缓存），如果没有这行代码，dp[100001]的定义纯属浪费空间
    return max_len;
}
int main(){
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) ans = max(ans,LIS(i)); //最长的LIS可能并不从第一个元素开始
    cout << ans;
    return 0;
}

加上了记忆化搜索但还是两个TLE 这个怎么做

严禁抄题解，发现后取消成绩

二分优化
#include<bits/stdc++.h>
using namespace std;
int n,b[100005],f[100005],d[100005],ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
	}
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=n;i++)
	{
		int now=lower_bound(d+1,d+n+1,b[i])-d;
		f[i]=now;
		d[now]=b[i];
		ans=max(ans,f[i]);
	}
	cout<<ans;
}

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。