简介

LIS（Longest Increasing Subsequence）：最长上升（不下降）子序列，有两种算法复杂度为O(n*logn)和O(n^2)。这种算法只能得到最终的数据个数，但是如果
需要得到具体的内容就不行了。由于第一种算法使用了2个for循环，所以算法的复杂度为O(n^2),该算法比较简洁易懂，但是复杂度较高。而第二种算法使用了一个for循
环和二分法，算法的复杂度为O(nlogn)。此算法虽稍微复杂，但是复杂度降了下来，在需要运算时间的情况下优先选择第二种算法。

思路以及代码详解

算法（nlogn）

思路（一）

假定存在一个序列d[1…9]=2 1 5 3 6 4 8 9 7，可以看出LIS长度为5。现在开始一步一步的找出来最终的结果。
　　定义序列B，令i=1…9来逐个考察。此外用变量len来记录现在最长算到了多少了。
　　首先，把d[1]放到B里，即B[1]=d[1]，就是说长度为1的LIS的最小末尾是2，这时len=1，然后把d[2]有序的放到B里，令B[1]=1（d[2]），就是说长度为1的LIS最
小末尾是1，d[1]=2已经没有用了，这时len=1不变。接着d[3]=5，5>1，所以令B[1+1]=d[3]=5，就是说长度为2的LIS的最小末尾是5，此时的B[1…2]=1,5，len=2。
　　再来，d[4]=3，它正好在1和5之间，当然放在1的位置上不合适，因为1<3，因此长度为2的最小末尾应该是3，淘汰掉5，这时候b[1...2]=1,3，len=2。 　　继续d[5]="6，它在3后边，所以B[3]=4，B[1...3]=1,3,6，len=3。" 　　第6个，d[6]="4，它加在3和6之间，所以我们把6换掉，这样B[1...3]=1,3,4，len=3。" 　　第7个，d[7]="8，8">4，所以B[4]=8，B[1…4]=1,3,4,8，len=4。
　　第8个，d[8]=9，B[1…5]=1,3,4,8,9，len=5。
　　最后一个，d[9]=7，所以B[1…5]=1,3,4,7,9，len=5。
　　注意这里的B并不是LIS，而是对应长度的LIS的最小末尾。
　　总结下：若后一个数比前一个数大，那么直接此数的后面，若后一个数比前一个数小，那么覆盖掉该数。最后得到的len就是LIS长度。

代码(一)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<bits/stdc++.h>
using namespace std;
#define maxn 100050
int a[maxn];
int ans[maxn];
int main(){
//	freopen("input.txt","r",stdin);
	int n; 
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	int len=1;
	ans[0]=a[0];
	for(int i=1;i<n;i++)
	{
		if(a[i]>=ans[len-1]) ans[len++]=a[i];
		else
		{
			int pos=upper_bound(ans,ans+len,a[i])-ans;
			ans[pos]=a[i];
		}
	}
	printf("%d\n",len);
	return 0;
}

算法（n^2）

思路（二）

再以数组a[0~8]={2,1,5,3,6,4,8,9,7}为例，先定义d[0]=1来存放LIS长度，接着从数组的第二个元素开始,每次都把d[i]定义为1，接着拿该元素之前的所有元素与它比较
，由于1<2,所以不进行额外的运算，d[1]依然是1。接着是第三个元素5，由于2<5，所以d[2]=d[0]+1=2，接着1也小于5，所以d[2]=d[1]+1=2。下一个元素为3，由于 1和2="" 都小于3，所以d[3]="d[0]+1=d[1]+1=2，但是5">3,所以最后的d[3]=2。接下来轮到元素6，由于之前的所有元素均小于6，所以d[4]=d[0]+1=d[1]+1=2，接着
d[4]=d[2]+1=d[3]+1=3，所以最后的d[4]为3。下面的元素为4，由于最多只轮到3<4，所以d[5]=d[3]+1=3。接下来同理d[6]=4,d[7]=5,d[8]=4。最后寻找数组d的
最大值，为5，所以LIS长度为5。
总结：用2个for循环，第一个for循环用来依次移动需要比较的元素，第二个for循环用来把该元素与之前的所有元素进行比较，d在该位置存放的长度为之前所有元素中最后一
个小于该元素且dp值最大的d存放的长度+1（表现出来的形式为该元素只要大于前面某个dp值最大的元素，那么d[j]立刻变为d[i]+1），若该元素小于之前所有的元素，那么该
位置存放的位置保持为1。

代码（二）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int d[1050],len;
	memset(d,0,sizeof(d));
	int n,a[1050];
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<n;i++)
	{
		int maxn=0;
		for(int j=i-1;j>=0;j--)
		{
			if(a[i]>=a[j])
				maxn=max(maxn,d[j]);
		}
		d[i]=maxn+1;
		len=max(len,d[i]);
	}
	printf("%d\n",len);
	return 0;
}

链接：ACM-HDOJ 1025题