[串和序列处理 7]LIS 最长递增子序列
LIS：给定一个字符串序列S={x0,x1,x2,...,x(n-1)}，找出其中的最长子序列，而且这个序列必须递增存在。
下面给出解决这个问题的几种方法：
(1) 转化为LCS问题
思想：将原序列S递增排序成序列T，然后利用动态规划算法取得S与T的公共最长子序列。具体算法详见《LCS最长公共子序列》。
效率：这个方法排序最好的是时间复杂度是O(n*logn)，动态规划解决LCS的时间复杂度是O(n^2)。因此总体时间复杂度是O(n*logn)+O(n^2)=O(n^2)级别。
(2) 分治策略
思想：假设f(i)表示S中 x0 ... xi 子串的最长递增子序列的长度。则有如下递归：找到所有在xi之前，且值小于xi 的元素xj，即j
f(i)=Max(f(j))+1. 其中{j | j
如果这样的j不存在，则xi自身构成一个长度为1的递增子序列。
该算法Java源代码如下：
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
{
sequence[i]=""+chars[i];
f[i]=1;//f[i]的最小值为1；
String temp="";
for(int j=0;j
{
if(chars[j]f[i]-1){
temp=temp+chars[j];
f[i]=f[j]+1;//更新f[i]的值。
}
}
sequence[i]=temp+sequence[i];
}
//打印结果
int maxLength=0;
int maxSize=0;
for(int k=0;k
if(maxLength
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();
}
}
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;if[i]-1){ temp=temp+chars[j]; f[i]=f[j]+1;//更新f[i]的值。 } } sequence[i]=temp+sequence[i]; } //打印结果 int maxLength=0; int maxSize=0; for(int k=0;k
效率：算法时间复杂度为O(n^2)级别。
(3) 动态规划算法
实际上这是一道很典型的动态规划问题。我们假设a[0]....a[i-1] 有一个最长递增子序列，其长度f(i-1)
那么对于a[0].... 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}，当增加a[4]的时候，如果a[4]>5，则两个子序列都需要增加a[4]；如果a[4]>3，则{1,2,3}+a[4]将必定成为新的最大子序列，而{1,2,5}不确定。因此我们看出，只要保存所有最大序列的最小的末尾元素即可。
因此我们设计一个如下的算法：其中b[k]用来表示最大子序列长度为k时的最小末尾元素。
Java代码
int LIS(){
b[1]=a[0];
for(int i=1;k=1;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]
for(int h=1,j=k;h!=j-1;){
if(b[k=(h+j)/2]
else j=k;
}
return j;
}
int LIS(){ b[1]=a[0]; for(int i=1;k=1;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]
该算法的时间复杂为O(N*logN)。