|
LIS：給定一個字符串序列S={x0,x1,x2,...,x(n-1)}，找出其中的最長子序列，而且這個序列必須遞增存在。 下面給出解決這個問題的幾種方法： (1) 轉(zhuǎn)化為LCS問題 思想：將原序列S遞增排序成序列T，然后利用動態(tài)規(guī)劃算法取得S與T的公共最長子序列。具體算法詳見《LCS最長公共子序列》。 效率：這個方法排序最好的是時間復(fù)雜度是O(n*logn)，動態(tài)規(guī)劃解決LCS的時間復(fù)雜度是O(n^2)。因此總體時間復(fù)雜度是O(n*logn)+O(n^2)=O(n^2)級別。 (2) 分治策略 思想：假設(shè)f(i)表示S中 x0 ... xi 子串的最長遞增子序列的長度。則有如下遞歸：找到所有在xi之前，且值小于xi 的元素xj，即j<i 且 xj<xi。如果這樣的元素存在，那么所有的xj 都有一個x0 ... xj 子串的最長遞增子序列，其長度為f(j)。把其中最大的f(j)選出來，則 f(i)=Max(f(j))+1. 其中{j | j<i 且xj<xi} 如果這樣的j不存在，則xi自身構(gòu)成一個長度為1的遞增子序列。 該算法Java源代碼如下：
package net.hr.algorithm.string;
/**
* 最長遞增子序列 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為末元素的最長遞增子序列長度為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();
}
}
效率：算法時間復(fù)雜度為O(n^2)級別。 (3) 動態(tài)規(guī)劃算法 實際上這是一道很典型的動態(tài)規(guī)劃問題。我們假設(shè)a[0]....a[i-1] 有一個最長遞增子序列，其長度f(i-1)<=i, 且該最長遞增子序列的最后一個元素為b。 那么對于a[0].... a[i] 而言，如果b<a[i]，那么f(i)=f(i-1)+1，且最長遞增子序列的最后一個元素變成了a[i]。如果b>=a[i]，那么f(i)=f(i-1)。 上面的過程有一個難點：如果a[0]....a[i-1] 有多個最大長度為f(i-1)的遞增子序列怎么辦？需不需要所有長度等于f(i-1)的遞增子序列的最后一個元素b0...bi全部存儲起來，再一一和a[i]比較大小呢？如果是這樣，那么整個算法與上面的分治策略將沒有什么不同了？ 事實上，并不需要怎么做。我們舉個例子： a[]={1、2、5、3、7} a[0] ... a[3] 的最大遞增子序列有兩個{1,2,5}和{1,2,3}，當(dāng)增加a[4]的時候，如果a[4]>5，則兩個子序列都需要增加a[4]；如果a[4]>3，則{1,2,3}+a[4]將必定成為新的最大子序列，而{1,2,5}不確定。因此我們看出，只要保存所有最大序列的最小的末尾元素即可。 因此我們設(shè)計一個如下的算法：其中b[k]用來表示最大子序列長度為k時的最小末尾元素。 Java代碼   
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;
}
該算法的時間復(fù)雜為O(N*logN)。 |
|
|
