时间复杂度为O(nlogn)的LIS算法

时间复杂度为 n*logn的LIS算法是用一个stack维护一个最长递增子序列

如果存在 x < y 且 a[x] > a[y],那么我们可以用a[y]去替换a[x]

因为a[y]比较小，具有更大的潜力，使得后面的元素和它成为更长的递增序列

如例子： a[] = {1,4,8,3,6};

我们用一个stack st保存当前的最长递增子序列,top = 0;

很明显，初始化时st[top] = 1;

之后随着i循环变量的递增，如果

a[i] > st[top] , 那么 st[++top] = a[i]. 很显然top+1就是当前最长递增子序列的长度

这样子判断的时间复杂度是O(1)，

为什么可以这样子判断？？？

因为st保存的是当前的最长递增子序列，所以如果a[i] > st[top] 那么a[i]可以加入st中

从而形成更长的最长递增子序列。

那么可能会有想法是，如果数据是1 5 3 4，很明显，最长递增子序列是1 3 4，

但是根据上面的想法是 1 5 形成最长递增子序列。

别担心

下面介绍当 a[i] < st[top]时的处理方法

上面我们说过，如果存在x < y 且 a[x] > a[y] 我们可以使用a[y]去替换a[x]

因为a[y] 具有更大的潜力,使得后面的元素和它成为更长的递增序列。

所以当 a[i] < st[top]时，显然 st中的元素就是a[x],而a[i]就是a[y]

我们在st中使用二分查找找到第一个大于等于a[i]的元素，然后用a[i]去替换它

比如 st = 1 , 4 , 8时

a[i] = 3,

我们可以用a[i]去替换4，从而在不影响结果的前提下，减少时间复杂度

题目uva10534

给定一个一组数字，要我们求这样一个序列

在序列的左边是递增的，右边是递减的，且递增和递减的个数要是一样的

思路：分别从两边进行最长递增子序列的dp，

dp1是从下标 0 -> n-1 进行dp

dp2是从下标 n-1 -> 0 进行dp

所以 ans = max{ min(dp1[i]-1, dp2[i]-1)+1, 0<=i<n };

但是题目的数据有1w，O(N*N）的算法是不行的，

所以要用nlogn的算法

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <algorithm>

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <map>

 #include <set>

 #include <string>

 using namespace std;

 typedef long long LL;

 const int INF = <<;

 const int N =  + ;

 int min(const int &a, const int &b)

 {

     return a < b ? a :b;

 }

 int max(const int &a, const int &b)

 {

     return a < b ? b : a;

 }

 int st[N];

 int top;

 void LIS(int *a, int n, int *dp)

 {

     int i,j;

     top = ;

     st[top] = a[];

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

     {

         if(a[i] > st[top])

         {

             st[++top] = a[i];

             dp[i] = top + ;

         }

         else

         {

             int low = , high = top;

             while(low <= high)

             {

                 int mid = (low + high) >> ;

                 if(st[mid]<a[i])

                     low = mid + ;

                 else

                     high = mid - ;

             }

             st[low] = a[i];

             dp[i] = low +;

         }

     }

 }

 int a[N];

 int dp[][N];

 int main()

 {

     int n,i,j;

     while(scanf("%d",&n)!=EOF)

     {

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

         {

             scanf("%d",&a[i]);

             dp[][i] = dp[][i] = ;

         }

         LIS(a,n,dp[]);

         int low = ,high = n - ;

         while(low < high)

         {

             int t = a[low];

             a[low] = a[high];

             a[high] = t;

             low ++;

             high --;

         }

         LIS(a,n,dp[]);

         int ans = ;

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

         {

             int t =  * min(dp[][i]-,dp[][n-i-]-) +;//因为第二次dp是将数组倒过来dp，所以要n-i-1

             ans = max(ans,t);

         }

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

     }

     return ;

 }

巴特西

时间复杂度为O(nlogn)的LIS算法

最新文章

热门文章