最长子序列问题（二分+贪心nlogn算法）

【题目描述】

给定N个数，求这N个数的最长上升子序列的长度。

【样例输入】

2 5 3 4 1 7 6

【样例输出】

什么是最长上升子序列？就是给你一个序列，请你在其中求出一段不断严格上升的部分，它不一定要连续。

就像这样：2,3,4,7和2,3,4,6就是序列2 5 3 4 1 7 6的两种选取方案。最长的长度是4.

什么是最长上升子序列？就是给你一个序列，请你在其中求出一段不断严格上升的部分，它不一定要连续。

就像这样：2,3,4,7和2,3,4,6就是序列2 5 3 4 1 7 6的两种选取方案。最长的长度是4.

思路：

新建一个low数组，low[i]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。因此，我们只需要维护low数组，对于每一个a[i]，如果a[i] > low[当前最长的LIS长度]，就把a[i]接到当前最长的LIS后面，即low[++当前最长的LIS长度]=a[i]。

那么，怎么维护low数组呢？

对于每一个a[i]，如果a[i]能接到LIS后面，就接上去；否则，就用a[i]取更新low数组。具体方法是，在low数组中找到第一个大于等于a[i]的元素low[j]，用a[i]去更新low[j]。如果从头到尾扫一遍low数组的话，时间复杂度仍是O(n^2)。我们注意到low数组内部一定是单调不降的，所有我们可以二分low数组，找出第一个大于等于a[i]的元素。二分一次low数组的时间复杂度的O(lgn)，所以总的时间复杂度是O(nlogn)。

代码如下：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <cmath>

using namespace std;

const int maxn =300003,INF=0x7f7f7f7f;

int low[maxn],a[maxn];

int n,ans;

int binary_search(int *a,int r,int x)

//二分查找，返回a数组中第一个>=x的位置

{

    int l=1,mid;

    while(l<=r)

    {

        mid=(l+r)>>1;

        if(a[mid]<=x)

            l=mid+1;

        else

            r=mid-1;

    }

    return l;

}

int main()

{

    scanf("%d",&n);

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

    {

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

        low[i]=INF;//由于low中存的是最小值，所以low初始化为INF

    }

    low[1]=a[1];

    ans=1;//初始时LIS长度为1

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

    {

        if(a[i]>=low[ans])//若a[i]>=low[ans]，直接把a[i]接到后面

            low[++ans]=a[i];

        else //否则，找到low中第一个>=a[i]的位置low[j]，用a[i]更新low[j]

            low[binary_search(low,ans,a[i])]=a[i];

    }

    printf("%d\n",ans);//输出答案

    return 0;

}

巴特西

最长子序列问题（二分+贪心nlogn算法）

最新文章

热门文章