求最长XX序列的两种方法

此类问题一般常用的有两种算法，时间复杂度分别是O(n^2)和O(nlogn)

第一种，普通算法，用一个标记数组标记包括当前数的最长序列的长度，然后往前递归寻找，此类方法这里不多说了

文章的dp问题里已经用过多次了

下面着重介绍一下一种省时但是不常用的算法，整体思想是DP+二分搜索，用一个b[k]=m 来标记

k长度的最长序列下，最小的数是m，比如有一序列 5 3 7 4

首先b[1]=5,初始化长度为1的序列就是第一个数，接下来到3的时候，3独立的长度为1的序列小于5，所以b[1]=3,

那么b[2]=4 因为长度为2的序列有两个5-7,3-7,3-4,期中序列最大的数最小的就是4了

因此，寻找大于当前数的一个b[]可以用二分来查找

在这里再转载一篇文章来详解一下吧
View Code

1 /* 2 题目大意：求一条最长的上升子序列.题目解答：用一般的0(n^2)超时，只能采用0(nlogn).我们先来回顾一下poj 1887 Testing the CATCHER是怎么做的。 3         ：首先我们确定了题目具有最优子结构，然后我们开始递归构造最优子结构，定义一个数组opt[i]表示前i个字符包含第i个字符的最长下降序列, 4         ：然后又最优子结构递归出最优解公式：opt[i]=max(opt[j]+1),num[i] < num[j] && 0<=j<i<m。但是由于子结构的无序性， 5         ：你只能遍历一遍寻出当中最大的可行解，导致复杂度一下子上升到n^2那我们再想问什么我们递归建立的子结构是不具有递增性或者说无序的呢， 6         ：原因在于我们定义它的时候就确定了这个结果的产生（opt[i]前i个字符包含第i个字符的最长下降序列）要想要包含第i个字符那就不可能一定 7         ：保证opt[i]>opt[i-1]。例如：2 5 4 1 opt[3]=2; opt[4]=1;那么我们怎么创建一个有序的最优子结构呢？？要保证opt[i]>=opt[i-1]设opt[i] 8         ：为前i个字符的最长子序列，这个显然不行，我们缺少子解得信息，无法更新，也就不能进行递归求解.那么求解一个n个字符的串，我们需要什么 9         ：信息？？1：第i个字符（这个属于源数据）。2：前i个字符的最长子序列 3：前i个字符的最长子序列的最优一个字符到底是多少？，如果有多个10         ：怎么办？先来看第三个条件的问题：如果有多个怎么办？例如 1 5 3 ....；前三个字符的最长子序列一看就知道是长度2，但是方案却又很多种11         ：{1,5}和{1,3}找那一种呢？当然是选取其中最小的一个，可以让目标增长的空间最大化3~无穷大>5~无穷大。好了现在三个条件都有了，关键的12         ：步骤来了，我们怎样存储2和3的两个条件opt[条件2]=[条件3]就是在前i个字符最长子序列.....(未完)13 14 Source Code15 16 Problem: 1631  User: wawadimu 17 Memory: 608K  Time: 110MS 18 Language: C++  Result: Accepted 19 20 Source Code 21  */22 #include<iostream>23  using namespace std;24 25  #define maxn 4001026  int num[maxn];27  int b[maxn];//b[k]=m ；长度为k的最长上升子序列中最小的数字值m28 int opt[maxn];//opt[k]=l；前k个数字最长上升子序列的长度l29 int p;//数组大小30 int main()31 {32     //freopen("1631.txt","r",stdin);33     int cas;34     int i,j,k;35     int l,r;36     int blen;//保存当前b数组的大小(即已经求得的最长的上升子序列)37     scanf("%d",&cas);38     while(cas--)39     {40         scanf("%d",&p);41         for(i=1;i<=p;i++)42             scanf("%d",&num[i]);43         b[1]=num[1];//只有一个数字是当然就是他本身44         blen=1;//长度45         for(i=1;i<=p;i++)//以此插入第i个数字46         {47             l=1; r=blen;48             while(l<=r)//寻找一个刚刚大于num[i]的b[k]49             {50                 int m=(l+r)>>1;51                 if(b[m] <num[i])52                     l=m+1;53                 else54                     r=m-1;55             }56             b[l]=num[i];//将大数字替换成小数字57             opt[i]=l;//更新前i个数字的最长大小58             blen = blen < l ? l : blen;//更新最长子序列长度59         }60         printf("%dn",blen);//输出答案61     }62     return 1;63 }

原文链接: https://www.cnblogs.com/void/archive/2011/05/08/2040332.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍