当前位置：首页 > news >正文

最长上升子序列LIS(一般+优化)

news 2025/7/17 9:38:13

1. 题目

题目链接：

B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

输入样例：

6
1 2 4 1 3 4

输出样例：

说明/提示：

分别取出 1、2、3、4 即可。

2. 具体实现

2.1 一般做法

dp[i]表示第i个位置的最长上升子序列个数

//思路：
//dp[i]表示第i个位置的最长子序列个数
//dp[i]也就是找到前面1到i-1位置上值小于a[i]的最大dp值 
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],dp[N]; 
int main(void){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];dp[i]=1;}int res=1;for(int i=2;i<=n;i++){int tmax=0;for(int j=1;j<i;j++){  //遍历前i-1项，找到值<a[i]的最大dp值 if(a[i]>a[j]) tmax=tmax>dp[j]?tmax:dp[j];}dp[i]=tmax+1;res=max(res,dp[i]);}cout<<res; return 0;
}

时间复杂度: O(n^2)
空间复杂度: O(N)

2.2 优化

dp[i]表示最长子序列长度为i的最小尾数

//思路2：
//dp[i]表示最长上升子序列长度为i的最小尾数
//显而易见，dp是一个递增序列
//我们对每一个数进行遍历
//每一次找到值大于a的位置进行更新即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;   //最小尾数最大页只能为1e6
int dp[N];
int a[5010]; 
int main(void){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}dp[1]=a[1];  //初始化 int ans=1;for(int i=1;i<=n;i++){//找到dp中值第一个大于a[i]的位置int t=lower_bound(dp+1,dp+1+ans,a[i])-dp; dp[t]=a[i];ans=max(ans,t);}cout<<ans; return 0;
}

时间复杂度: O(nlog⁡n)
空间复杂度: O(n)