当前位置: 代码迷 >> 综合 >> 【LIS 模板】
  详细解决方案

【LIS 模板】

热度:8   发布时间:2024-01-18 01:45:49.0

1、复杂度0(n^2):

定义dp[i]:以ai为结尾的最长上升子序列的长度

以ai结尾的上升子序列是:
①只包含ai的子序列
②在满足j<i并且aj<ai的以aj为结尾的上升子列末尾,追加上ai后得到的子序列

综合以上两种情况,便可以得到递推关系式:

dp[i] = max{1, dp[j]+1| j<i且aj<ai}


代码实现:

//O(n^2)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 30010;
int dp[maxn], a[maxn];
int main()
{int n;while(scanf("%d",&n)!=EOF){for(int i=0;i<n;++i)  scanf("%d",&a[i]);  int ans=0;  for(int i=0;i<n;++i)  {  dp[i]=1;  for(int j=0;j<i;++j)  {  if(a[j]<a[i])  dp[i] = max(dp[i], dp[j]+1);  }   ans=max(dp[i],ans);  }  printf("%d\n",ans);  }return 0;
} 



2、复杂度0(nlogn):

定义dp[i]:长度为i+1的上升子序列中末尾元素的最小值(不存在就是INF)
最开始全部dp[i]的值都初始化为INF。然后由前到后逐个考虑数列的元素,对于每个aj,如果i=0或者dp[i-1]<aj的话,就用dp[i]=min(dp[i],aj)进行更新。最终找出使得dp[i]<INF的最大的i+1就是结果了。

代码实现:

//O(nlogn)
#include <cstdio>  
#include <algorithm>  
#define INF 0x3f3f3f  
using namespace std;  
int dp[30010],a[30010];  
int main()  
{  int n,i,j;  while(scanf("%d",&n)!=EOF)  {  for(i=0;i<n;++i)  {  scanf("%d",&a[i]);  dp[i]=INF;  }  for(i=0;i<n;++i)  *lower_bound(dp,dp+n,a[i])=a[i];  printf("%d\n",lower_bound(dp,dp+n,INF)-dp);   }  return 0;  
}   



  相关解决方案