最长上升子序列（LIS）的两种算法_最长上升子序列算法

dp[i]表示以ai为末尾的最长上升子序列的长度，而以ai结尾的最长上升子序列有两种：1.只包含ai的子序列;  2.在满足j<i且aj<ai的以aj为结尾的上升子序列末尾，追加上ai得到的子序列。

递推关系：

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

　　让我们举个例子：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度。

　　前1个数 d(1)=1 子序列为2；

　　前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7

　　前3个数 在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1

　　前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5

　　前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6

　　前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4

　　前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3

　　前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8

　　前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9

　　d(i)=max{d(1),d(2),……,d(i)} 我们可以看出这9个数的LIS为d(9)=5

　　总结一下，d(i)就是找以A[i]结尾的，在A[i]之前的最长上升子序列+1，当A[i]之前没有比A[i]更小的数时，d(i)=1。所有的d(i)里面最大的那个就是最长上升子序列。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[10010];
int dp[10010];
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
			dp[i]=1;
		}
		int ans=0;
		for(int i=1;i<n;i++)
		{
			for(int j=0;j<i;j++){
				if(a[j]<a[i])
				   dp[i]=max(dp[j]+1,dp[i]);	
			}
			ans=max(ans,dp[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
 } 

还有一种时间复杂度为〇(nlogn)的算法，下面就来看看。

我们再举一个例子：有以下序列A[]=3 1 2 6 4 5 10 7，求LIS长度。

　　我们定义一个B[i]来储存可能的排序序列，len为LIS长度。我们依次把A[i]有序地放进B[i]里。（为了方便，i的范围就从1~n表示第i个数）

　　A[1]=3，把3放进B[1]，此时B[1]=3，此时len=1，最小末尾是3

　　A[2]=1，因为1比3小，所以可以把B[1]中的3替换为1，此时B[1]=1，此时len=1，最小末尾是1

　　A[3]=2，2大于1，就把2放进B[2]=2，此时B[]={1,2}，len=2

　　同理，A[4]=6，把6放进B[3]=6，B[]={1,2,6}，len=3

　　A[5]=4，4在2和6之间，比6小，可以把B[3]替换为4，B[]={1,2,4}，len=3

　　A[6]=5，B[4]=5，B[]={1,2,4,5}，len=4 

　　A[7]=10，B[5]=10，B[]={1,2,4,5,10}，len=5

　　A[8]=7，7在5和10之间，比10小，可以把B[5]替换为7，B[]={1,2,4,5,7}，len=5

　　最终我们得出LIS长度为5。但是，但是！！这里的1 2 4 5 7很明显并不是正确的最长上升子序列。是的，B序列并不表示最长上升子序列，它只表示相应最长子序列长度的排好序的最小序列。这有什么用呢？我们最后一步7替换10并没有增加最长子序列的长度，而这一步的意义，在于记录最小序列，代表了一种“最可能性”。假如后面还有两个数据8和9，那么B[6]将更新为8，B[7]将更新为9，len就变为7。

因为在B中插入的数据是有序的，不需要移动，只需要替换，所以可以用二分查找插入的位置，那么插入n个数的时间复杂度为〇(logn)，这样我们会把这个求LIS长度的算法复杂度降为了〇(nlogn)。

int put(int arr[], int l, int r, int key)//在arr[l...r]中二分查找插入位置
{
    int mid;
    if (arr[r] <= key)
        return r + 1;
    while (l < r)
    {
        mid = l + (r - l) / 2;
        if (arr[mid] <= key)
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}
 
int LIS(int A[], int n)
{
    int i = 0, len = 1 ,next;
    int* B = (int *)alloca(sizeof(int) * (n + 1));
    B[1] = A[0]; 
    for (i = 1;i < n;i++)
    {
        int next = put(B, 1, len, A[i]); 
        B[next] = A[i];
        if (len < next)    len = next;
    }
    return len;
}

二.O(nlogn)算法，dp[i]=长度为i+1的上升子序列中末尾元素的最小值（不存在的话就是INF）

这种算法中，运用STL中的lower_bound()函数很方便。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f
int dp[10010];//dp[i]表示长度为i+1的子序列末尾元素最小值； 
int a[10010];
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			dp[i]=INF;//不可以用memset对数组赋值INF,只能赋值0或-1；
			          //可以用fill(dp,dp+n,INF); 
		}
		for(int i=0;i<n;i++)
		{
			*lower_bound(dp,dp+n,a[i])=a[i];//找到>=a[i]的第一个元素，并用a[i]替换； 
		}
		printf("%d\n",lower_bound(dp,dp+n,INF)-dp);//找到第一个INF的地址减去首地址就是最大子序列的长度； 
	}
	return 0;
}

还有一种代码：

for(int i=1;i<=n;i++)  
{  
    int k=lower_bound(g+1,g+n+1,a[i])-g;//从存储序列的末尾元素中找出第一个大于或等于a[i]的位置，
		                        //K就是以a[i]结尾的最长上升子序列的长度，此时g是从1开始不用+1；  
    dp[i]=k;  
    g[k]=min(g[k],a[i]);//末尾元素每次都取最小的，保证序列尽可能长；   
    ans=max(dp[i],ans);//找出序列长度的最大值就是最长序列；   
}  

copy的※夏日星空※和Alinshans的蟹蟹大神