LIS：給定一個(gè)字符串序列S={x0,x1,x2,...,x(n-1)}，找出其中的最長(zhǎng)子序列，而且這個(gè)序列必須遞增存在。

下面給出解決這個(gè)問(wèn)題的幾種方法：

(1) 轉(zhuǎn)化為L(zhǎng)CS問(wèn)題

思想：將原序列S遞增排序成序列T，然后利用動(dòng)態(tài)規(guī)劃算法取得S與T的公共最長(zhǎng)子序列。具體算法詳見《LCS最長(zhǎng)公共子序列》。

效率：這個(gè)方法排序最好的是時(shí)間復(fù)雜度是O(n*logn)，動(dòng)態(tài)規(guī)劃解決LCS的時(shí)間復(fù)雜度是O(n^2)。因此總體時(shí)間復(fù)雜度是O(n*logn)+O(n^2)=O(n^2)級(jí)別。

(2) 分治策略

思想：假設(shè)f(i)表示S中 x0 ... xi 子串的最長(zhǎng)遞增子序列的長(zhǎng)度。則有如下遞歸：找到所有在xi之前，且值小于xi 的元素xj，即j<i 且 xj<xi。如果這樣的元素存在，那么所有的xj 都有一個(gè)x0 ... xj 子串的最長(zhǎng)遞增子序列，其長(zhǎng)度為f(j)。把其中最大的f(j)選出來(lái)，則

f(i)=Max(f(j))+1. 其中{j | j<i 且xj<xi}

如果這樣的j不存在，則xi自身構(gòu)成一個(gè)長(zhǎng)度為1的遞增子序列。

該算法Java源代碼如下：

package net.hr.algorithm.string;
/**
 * 最長(zhǎng)遞增子序列 LIS
 * @author heartraid
 */
public class LIS {

	char[] chars=null;
	
	public LIS(String str){
		chars=str.toCharArray();
	}
	
	public void getLIS(){
	     
		int[] f=new int[chars.length]; //用于存放f(i)值
		String[] sequence=new String[chars.length];
		f[0]=1; //以第x1為末元素的最長(zhǎng)遞增子序列長(zhǎng)度為1

		for(int i=1;i<chars.length;i++)//循環(huán)n-1次
		{
			sequence[i]=""+chars[i];
			f[i]=1;//f[i]的最小值為1；
			String temp="";
			for(int j=0;j<i;j++)//循環(huán)i 次
			{
				
				if(chars[j]<chars[i]&&f[j]>f[i]-1){
					temp=temp+chars[j];
					f[i]=f[j]+1;//更新f[i]的值。
				}
				
			}
			sequence[i]=temp+sequence[i];
		}
		//打印結(jié)果
		int maxLength=0;
		int maxSize=0;
		for(int k=0;k<chars.length;k++){
			if(maxLength<f[k]){
				maxLength=f[k];
				maxSize=k;
			}
		}
		System.out.println("最大遞增子序列為："+sequence[maxSize]+"(length="+maxLength+")"); 
	}

	public static void main(String[] args) {
		LIS lis=new LIS("ijabcsrewesdsdewg");
		lis.getLIS();
		
	}

}

效率：算法時(shí)間復(fù)雜度為O(n^2)級(jí)別。

(3) 動(dòng)態(tài)規(guī)劃算法

實(shí)際上這是一道很典型的動(dòng)態(tài)規(guī)劃問(wèn)題。我們假設(shè)a[0]....a[i-1] 有一個(gè)最長(zhǎng)遞增子序列，其長(zhǎng)度f(wàn)(i-1)<=i, 且該最長(zhǎng)遞增子序列的最后一個(gè)元素為b。

那么對(duì)于a[0].... a[i] 而言，如果b<a[i]，那么f(i)=f(i-1)+1，且最長(zhǎng)遞增子序列的最后一個(gè)元素變成了a[i]。如果b>=a[i]，那么f(i)=f(i-1)。

上面的過(guò)程有一個(gè)難點(diǎn)：如果a[0]....a[i-1] 有多個(gè)最大長(zhǎng)度為f(i-1)的遞增子序列怎么辦？需不需要所有長(zhǎng)度等于f(i-1)的遞增子序列的最后一個(gè)元素b0...bi全部存儲(chǔ)起來(lái)，再一一和a[i]比較大小呢？如果是這樣，那么整個(gè)算法與上面的分治策略將沒(méi)有什么不同了？

事實(shí)上，并不需要怎么做。我們舉個(gè)例子： a[]={1、2、5、3、7}

a[0] ... a[3] 的最大遞增子序列有兩個(gè){1,2,5}和{1,2,3}，當(dāng)增加a[4]的時(shí)候，如果a[4]>5，則兩個(gè)子序列都需要增加a[4]；如果a[4]>3，則{1,2,3}+a[4]將必定成為新的最大子序列，而{1,2,5}不確定。因此我們看出，只要保存所有最大序列的最小的末尾元素即可。

因此我們?cè)O(shè)計(jì)一個(gè)如下的算法：其中b[k]用來(lái)表示最大子序列長(zhǎng)度為k時(shí)的最小末尾元素。

Java代碼

1. int LIS(){
2. b[1]=a[0];
3. for(int i=1;k=1;i<n;i++){
4. if(a[i]>=b[k]) b[++k]=a[i];
5. else b[binary(i,k)]=a[i];
6. }
7. return k;
8. }
10. int binary(int i, int k){
11. if(a[i]<b[1]) return 1;
12. for(int h=1,j=k;h!=j-1;){
13. if(b[k=(h+j)/2]<=a[i]) h=k;
14. else j=k;
15. }
16. return j;
17. }

int LIS(){
   b[1]=a[0];
   for(int i=1;k=1;i<n;i++){
      if(a[i]>=b[k]) b[++k]=a[i];
      else b[binary(i,k)]=a[i];
   }
   return k;
}

int binary(int i, int k){
   if(a[i]<b[1]) return 1;
   for(int h=1,j=k;h!=j-1;){
      if(b[k=(h+j)/2]<=a[i]) h=k;
      else j=k;  
   }
   return j;
} 

該算法的時(shí)間復(fù)雜為O(N*logN)。