前言

Updated 2025/3/25 更新了 $O(n \log n)$ 的代码。

内容写作不易，求赞！

题目大意

就是对于给定的序列，求出最长上升子序列的长度。

思路1

搜索题，直接暴力，然后 AC 3个点，其他 TLE。

代码：

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

const int N = 1e6 + 10;

int ans, a[N], n;

int dfs(int x)
{
	if(a[x] == a[n]) return 1;
	int maxn = 1;
	for(int i = x + 1;i <= n;i++)
		if(a[i] > a[x]) 
			maxn = max(maxn, dfs(i) + 1);
	return maxn;
}

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= n;i++) ans = max(ans, dfs(i));
	cout << ans << endl;
	return 0;
}

思路2

顺着思路1，想优化。

不难想到用记忆化搜索。

说白了就是新开一个数组，然后记录每次的最大值。

成功 AC！

代码：

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

const int N = 1e6 + 10;

int ans, a[N], n, b[N];

int dfs(int x)
{
	if(b[x] != 0) return b[x];
	if(a[x] == a[n]) return 1;
	int maxn = 1;
	for(int i = x + 1;i <= n;i++)
		if(a[i] > a[x]) 
			maxn = max(maxn, dfs(i) + 1);
	b[x] = maxn;
	return maxn;
}

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= n;i++) ans = max(ans, dfs(i));
	cout << ans << endl;
	return 0;
}

思路3

这里还没完呢qwq

不难发现，这是一道 线性 DP 的板子题。

说白了就是：用双重循环做一个迭代。时间复杂度：$O(n^2)$。

还是可以 AC！

代码：

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

const int N = 1e6 + 10;

int a[N], n, b[N] = {0, 1}, ans;

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= n;i++)
	{
		b[i] = 1;
		for(int j = 0;j < i;j++)
			if(a[i] > a[j])
				b[i] = max(b[i], b[j] + 1);
		ans = max(ans, b[i]);
	}
	cout << ans;
	return 0;
}

思路4

使用二分查找即可！时间复杂度：$O(n \log n)$

还是可以 AC！

代码：

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

const int N = 1e6 + 5;
int a[N], b[N] = {-1}, l, n;

int main()
{
	cin >> n;
	for(int i = 0;i < n;i++) cin >> a[i];
	for(int i = 0;i < n;i++)
	{
		int p = lower_bound(b, b + l, a[i]) - b;
		b[p] = a[i];
		if(p == l) l++;
	}
	cout << l << endl;
	return 0;
}

题意

不日，经典模板题你让我写题意？

思路1

谨防写死路有人给我点差评（实际上我的死路和歹马只是 不是最优解 ，而 不是错误 ，还有一些死路和歹马是为了给大家讲解一些错误歹马并分析它们为什么错，以避免换个题型犯了 经典错误 ）。

一个递归解决。

对于从0到i的最长子序列，用f(i)表示，当i==0时返回1，其他的就往前找，判断f(0)到f(i-1)的最大+1（因为要加上本次）。

但这样会TLE。

所以加个记忆化，如果访问过就输出访问结果，否则再算，然后i==0直接在访问数组标成1就好了。

代码1

#include<iostream>
using namespace std;
int n;
int a[int(2e3)];
int v[int(2e3)]={1};//标i==0的访问
int main(){
	int f(int);
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	int ans=0;
	for(int i=0;i<n;i++)
		ans=max(ans,f(i));//寻找最大
	cout<<ans;
}
int f(int n){
	if(v[n])//如果访问过
		return v[n];
	int ret=1;
	for(int i=0;i<n;i++)
		if(a[i]<a[n])//只要是同序列
			ret=max(ret,f(i)+1);
	v[n]=ret;
	return ret;
}

思路2

果断DP

思路一致改成DP。

思路3

DP的第二种想法

用$f_i$表示从$a_0$到$a_i$的最长子序列。

算$f_i$只需要往前找最大值+1。

大师为题

代码2

#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	int f[n];
	fill(f,f+n,1);//最短为1，与前面ret=1异曲同工
	int maxs=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++)
			if(a[j]<a[i])
				f[i]=max(f[i],f[j]+1);
		maxs=max(maxs,f[i]);
	}
	cout<<maxs;
}

$O(n log n)$ 解法

#include<cstdio>
#include<algorithm> //lower_bound()
#define N 1001

using namespace std;

int a[N],LIS[N],n,cnt=-1;

int main()
{
	scanf("%d",&n);
	
	for(int i=0;i<n;++i)
		scanf("%d",&a[i]);		//读入 
		
	for(int i=0;i<n;++i)
	{
		if(cnt==-1 || LIS[cnt]<a[i])
			LIS[++cnt]=a[i];	//如果序列为空或者这个数本身大于序列最后一个数，直接插入 
		else
			*lower_bound(LIS,LIS+cnt+1,a[i])=a[i];	//否则，替换掉 lower_bound 的位置的数 
	}
	
	printf("%d",cnt+1);	//因为 cnt 从 -1 开始，所以输出时 +1 
	
	return 0;
}

题意

求出最长上升子序列的长度

思路

参照"模拟"的思路

循环每个数,使这个数是这段序列的最后一个

求出这个范围中最长上升子序列的长度

模拟

参考代码

输入 
7

输入
1 7 3 5 9 4 8

初始
1 1 1 1 1 1 1

第一次
1 2 1 1 1 1 1

第二次
1 2 2 1 1 1 1

第三次
1 2 2 3 1 1 1

第四次
1 2 2 3 4 1 1

第五次
1 2 2 3 4 3 1

第六次
1 2 2 3 4 3 4

最大值为4(注意,不是最后一个)

输出
4

代码

#include<iostream>
using namespace std;
int n;
int a[114514];//存储每个数字
int dp[114514];//DP状态数组
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];//输入
		dp[i]=1;//初始化
	}
	dp[0]=1;//边界
	for(int i=1;i<n;i++)//每一个数字当最后的时候
	{
		for(int j=0;j<i;j++)
		{
			if(a[j]<a[i])//如果小于前n-j
			{
				dp[i]=max(dp[i],dp[j]+1);//更新状态
			}
		}
	}
	int ma=0;
	for(int i=0;i<n;i++)//获得最长上升子序列
	{
		ma=max(ma,dp[i]);
	}
	cout<<ma;//输出(注意,不是最后一个)
	return 0;//完结散花
}

题意

找最长的上升子序列（不是最大的数）

上升子序列：如果 $i > j$ 且 $a_i > a_j$，那么它们是上升的子序列

PS：子序列是 $i > j$，子串才是 $i = j + 1$（说人话就是子序列可以不连续，子串是必须连续）

思路

$f_i$ 记录从第 1 个到第 $i$ 个数的最长子序列

这里找 $f_i$ 要找 1 到 $i$ 最长的子序列（$f_j$），而不是找最大的数（$a_j$）

代码

#include <bits/stdc++.h>
using namespace std;
int a[1005],f[1005],mx;
int main(int argc, char **argv){
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		f[i] = 1;	// 最少可以有一个长度（初始化）
		for (int j = 1;j <= i;j++){	// ⭐要找的是最长的序列，不是最大的数
			// 如果当前的数大于在找的这个数，那么对比序列长度
			if (a[i] > a[j])	f[i] = max(f[i],f[j] + 1);
		}
		mx = max(mx,f[i]);	// 最长序列长度
	}
	cout << mx;
	return 0;
}

帮陈老师发一个DFS题解。下面是优美的代码：

#include<bits/stdc++.h>
using namespace std;
int n, ans = 0;
int a[1005];
int mem[1005];

int dfs(int x) {
    if(x == 0) return 1;
    if(mem[x] != -1) return mem[x];
    int cnt = 1;
    for(int i = x - 1; i >= 0; i--) {
        if(a[i] < a[x]) {
            cnt = max(cnt, dfs(i) + 1);
        }
    }
    mem[x] = cnt;
    return cnt;
}

int main() {
    cin >> n;
    memset(mem, -1, sizeof(mem));
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n; i++) {
        ans = max(ans, dfs(i));
    }
    cout << ans;
    return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
int arr[10010],arr2[10010];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) arr2[i]=1,cin>>arr[i];
    for(int i=0;i<n;i++){
        int ok[1001],t=0;
        for(int j=0;j<=i;j++){
            if(arr[i]>arr[j]){
                ok[t++]=arr2[j]+1;
            }
        }
        int maxx=0;
        for(int i=0;i<t;i++) maxx=max(ok[i],maxx);
        arr2[i]=maxx;
    }
    sort(arr2,arr2+n);
    cout<<arr2[n-1]+1;
    return 0;
}

非一本通

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int k[1005];
int ans;
int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	fill(k,k+n,1);
	for(int i=1;i<n;i++) for(int j=0;j<i;j++) if(a[i]>a[j]) k[i]=max(k[i],k[j]+1);
	for(int i=0;i<n;i++) ans=max(ans,k[i]);
	cout<<ans<<"\n";
	return 0;
}

AC呆马：

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

const int maxn = 1e3 + 5;
int a[maxn],d[maxn];

int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= n; i++)
		d[i] = 1;
	int ans = 1;
	for(int i = 2; i <= n; i++)
	{
		for(int j = 1; j < i; j++)
		{
			if(a[j] < a[i])
				d[i] = max(d[i], d[j] + 1);
		}
	}
	for(int i = 1; i <= n; i++)
		ans = max(d[i], ans);
	cout << ans << endl;
	return 0;
}

参考荷韵蕊和皇民者的

看题解的建议分析看荷韵蕊，代码看皇民者

荷韵蕊代码太垃圾了

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n+1]={},f[n+1]={},maxs=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i]=1;
		for(int j=1;j<i;j++)
		{
			if(a[i]>a[j])
			{
				f[i]=max(f[i],f[j]+1);
			}
		}
		maxs=max(maxs,f[i]);
	}
	cout<<maxs;
}