LIS(两种方法求最长上升子序列)

首先得明白一个概念：子序列不一定是连续的，可以是断开的。

有两种写法：

一、动态规划写法

复杂度：O(n^2)

代码：

 #include <iostream>

 #include <queue>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #define INF 0x3f3f3f3f

 using namespace std;

 typedef long long ll;

 const int maxn = ;

 int a[maxn],dp[maxn];

 int main()

 {

     ios::sync_with_stdio(false);

     int n;

     while(cin>>n && n)

     {

         for(int i = ; i<n; i++)

             cin>>a[i];

         int mmax = -;

         for(int i = ; i<n; i++)

         {

             dp[i] = ;

             for(int j = ; j<i; j++)//遍历之前的每一个元素pre

             {

                 if(a[j]<a[i] && (dp[j]+>dp[i]))//如果元素pre < 当前元素cur,而且pre的长度+1要比当前的长度多就更新当前的长度

                 {

                     dp[i] = dp[j]+;

                 }

             }

             mmax = max(mmax,dp[i]);//维护最大的长度

         }

         printf("%d\n",mmax);

     }

     return ;

 }

二、low_bound写法

复杂度：O(nlogn)

这种写法就是将动规写法中的第二层的遍历改为了二分查找。所以复杂度变为O(nlogn)

牛客讲解视频

该算法中开了一个辅助数组h来表示该长度下最后的元素的最小值。例如 1、2、0、5 、-1

为什么要修改h数组里边的数为小的值呢，因为修改后h数组能变长的潜力就增大了，所以要修改。

代码：

 #include <iostream>

 #include <queue>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #define INF 0x3f3f3f3f

 using namespace std;

 typedef long long ll;

 const int maxn = ;

 int a[maxn],dp[maxn];

 int main()

 {

     ios::sync_with_stdio(false);

     int n;

     while(cin>>n)

     {

         memset(a,,sizeof(a));

         for(int i = ; i<n; i++)

             dp[i] = INF;

         for(int i = ; i<n; i++)

             cin>>a[i];

         int mmax = -;

         for(int i = ; i<n; i++)

         {

             int k = lower_bound(dp, dp+n, a[i])-dp;

             dp[k] = a[i];

             mmax = max(mmax, k+);

         }

         printf("%d\n",mmax);

     }

     return ;

 }

巴特西

LIS(两种方法求最长上升子序列)

最新文章

热门文章