LIS小结（O(∩_∩)O~哄哄）

~(≧▽≦)/~啦啦啦，昨天说的是LCS，今天我们要学习的是LIS，什么是LIS呢？

LIS： 最长有序子序列（递增／递减／非递增／非递减）这么说还是有些模糊，举个例子：

在一个无序的序列a1,a2,.....,am里，找到一个最长的序列，满足ai<=aj...<=ak; 且i<j<k;

例如该无序子序列为a[1]=1,a[2]=4,a[3]=5,a[4]=2;则最长序列为1,4,5.

小盆友们是不是明白了什么是最长有序子序列了呢？下面我们说说怎么求最长有序子序列：

先来说说经典的求法吧：

设a[i]表示序列中的第i个数，f[i]表示从1到i这一段中以i结尾的最长上升子序列的长度，初始时设f[i] = 0(i = 1, 2, ..., len(A))。则有动态规划方程：f[i] = max{1, f[j] + 1} (j = 1, 2, ..., i - 1, 且a[j] < a[i])。

现在，我们仔细考虑计算f[i]时的情况。假设有两个元素a[x]和a[y]，满足

(1)y < x < i

(2)a[x] <a[y] < a[i]

(3)f[x] = f[y]

此时，选择f[x]和选择f[y]都可以得到同样的f[i]值，那么，在最长上升子序列的这个位置中，应该选择a[x]还是应该选择a[y]呢？

　很明显，选择a[x]比选择a[y]要好。因为由于条件a[x] < a[y] < a[i]，在a[x+1] ~a[i-1]这一段中，如果存在a[z]，a[x] < a[z] < a[y]，则与选择a[y]相比，将会得到更长的上升子序列。

　　再根据条件f[x] = f[y]，我们会得到一个启示：根据f[]的值进行分类。对于f[]的每一个取值k，我们只需要保留满足f[i] = k的所有a[i]中的最小值。设d[k]记录这个值，即d[k] = min{ a[i] } ( f[i] = k )。

特别关注D[]的几个特点：

(1)　D[k]的值是在整个计算过程中是单调不上升的。//此处需要特别注意!!!关键之所在!

　　(2)　D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。

利用D[]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断a[i]与D[len],若a[i] > D[len]，则将a[i]接在D[len]后将得到一个更长的上升子序列,len = len + 1,D[len+1] = a[i];否则,在D[1]..D[len]中,找到最大的j,满足D[j] < a[i].令k = j + 1,则有D[j] < a[i] <= D[k]，将a[i]接在D[j]后将得到一个更长的上升子序列,同时更新D[k] = a[i].最后，len即为所要求的最长上升子序列的长度。

在上述算法中,若使用朴素的顺序查找在D[1]..D[len]查找,由于共有O(n)个元素需要计算,每次计算时的复杂度是O(n),则整个算法的时间复杂度为O(n^2),与原来的算法相比没有任何进步.但是由于D[]的特点a[x] <a[y] < a[i],我们在D[]中查找时,可以使用二分查找高效地完成,则整个算法的时间复杂度下降为O(nlogn),有了非常显著的提高.需要注意的是,D[]在算法结束后记录的并不是一个符合题意的最长上升子序列.

这个算法还可以扩展到整个最长子序列系列问题,整个算法的难点在于二分查找的设计,需要非常小心注意.

 1 // By Fandywang 2008.7.21
 2 // Call: LIS(a, n); 求最大递增/上升子序列(如果为最大非降子序列,只需把上面的注释部分给与替换)
 3 const int N = 1001;
 4 int a[N], f[N], d[N]; // d[i]用于记录a[0...i]的最大长度
 5 int bsearch(const int *f, int size, const int &a)
 6 {
 7     int l=0, r=size-1;
 8     while( l <= r )
 9     {
10         int mid = (l+r)/2;
11         if( a > f[mid-1] && a <= f[mid] ) return mid; // >&&<= 换为: >= && <
12         else if( a < f[mid] ) r = mid-1;
13         else l = mid+1;
14     }
15 }
16 int LIS(const int *a, const int &n){
17      int i, j, size = 1;
18      f[0] = a[0]; d[0] = 1;
19      for( i=1; i < n; ++i ){
20           if( a[i] <= f[0] ) j = 0;                 // <= 换为: <
21          else if( a[i] > f[size-1] ) j = size++;   // > 换为: >=
22          else j = bsearch(f, size, a[i]);
23          f[j] = a[i]; d[i] = j+1;
24      }
25      return size;
26 }

上面的算法多少有些繁琐，下面介绍另一种算法：

如果前i-1个数中的最长非降子序列的最后一个数是ak;那么下一步就是在求前k-1个数中的的最长非降子序列；

因此我们可以设计一个状态opt[j]表示前i个数中用到a[i]所构成的最优解。

那么决策就是在前i-1个数中找到最大的opt[j] 使得a[j]<=a[i]，那么opt[j]+1 就是opt[i]的值;

方程可以这样表示：

　　　　　　max[opt[j]] a[i] < a[j] && 0<=j<i

opt[i] ={

　　　　　　max[opt[j]]+1 a[i] >= a[j] && 0<=j<i

 1 #include <stdio.h>
 2 
 3 #include <stdlib.h>
 4 
 5  
 6 
 7 int main()
 8 
 9 {   
10 
11     int seq[10] = {4,5,7,8,3,2,6,7,33,4};
12 
13     int opt[10], i, j, max = 0;
14 
15  
16 
17     for(i=0; i<10; i++)
18 
19         opt[i] = 0;
20 
21     opt[0] = 1;  //只有一个数时最长非降序列长度为1
22 
23  
24 
25     for(i=1; i<10; i++)
26 
27 　　{
28 
29 　　　　　opt[i] = 1;
30 
31         for(j=0; j<i; j++)
32 
33         {
34 
35             if(seq[j]<=seq[i] && opt[j]+1>opt[i])
36 
37             {
38 
39                 opt[i] = opt[j]+1;
40 
41             }
42 
43         }
44 
45 　　}
46 
47  
48 
49     for(i=0; i<10; i++)
50 
51         if(opt[i] > max)
52 
53             max = opt[i];
54 
55     printf("max:%d
", max);
56 
57     return 0;
58 
59 }

感谢：

http://www.cnblogs.com/dartagnan/archive/2011/08/29/2158230.html

http://hi.baidu.com/fandywang_jlu/item/da673a3d83e2a65980f1a7e1

————Anonymous.PJQ