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<i 且 xj<xi。如果这样的元素存在,那么所有的xj 都有一个x0 ... xj 子串的最长递增子序列,其长度为f(j)。把其中最大的f(j)选出来,则
f(i)=Max(f(j))+1. 其中{j | j<i 且xj<xi}
如果这样的j不存在,则xi自身构成一个长度为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++)//循环n-1次
{
sequence[i]=""+chars[i];
f[i]=1;//f[i]的最小值为1;
String temp="";
for(int j=0;j<i;j++)//循环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];
}
//打印结果
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();
}
}
效率:
算法时间复杂度为O(n^2)级别。
(3) 动态规划算法
实际上这是一道很典型的动态规划问题。我们假设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},当增加a[4]的时候,如果a[4]>5,则两个子序列都需要增加a[4];如果a[4]>3,则{1,2,3}+a[4]将必定成为新的最大子序列,而{1,2,5}不确定。因此我们看出,只要保存所有最大序列的最小的末尾元素即可。
因此我们设计一个如下的算法:其中b[k]用来表示最大子序列长度为k时的最小末尾元素。
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;
}
该算法的时间复杂为O(N*logN)。
分享到:
相关推荐
使用动态规划思想求出最长单调递增子序列(LIS),时间复杂度为O(n log k)
下面小编就为大家带来一篇LIS 最长递增子序列 Java的简单实现。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 Visual Studio 2012 项目包 使用4种不同的方法实现最长递增子序列
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 实验报告 使用4种不同的方式实现最长递增子序列
我写的LIS算法,有两种思路,程序全在这个cpp文件中,可以运行
##算法最长递增子序列时间复杂度O(nlogn)##接口JAVA swing ##功能更改输入字符串的长度随机生成输入字符串标记输入字符串中最长的递增子序列
1. 定义状态: 2. 状态转移方程: 3. 初始化: 4. 输出: 5. 空间优化: 1 .定义新状态: 2. 状态转移方程: 3. 初始化: 4. 输出:
最长上升子序列(Longest Increasing Subsequence,简称LIS)是指在一个序列中找到一个最长的子序列,使得子序列中的元素是递增排列的。这个问题在计算机科学中很常见,有多种解决方法,其中动态规划是最常用的方法...
这时候B[1..2] = 1, 5,Len=2再来,d[4] = 3,它正好加在1,5之间,放在1的位置显然不合适,因为1小于3,长度为1的LIS最小末尾应该是
还提供了一个用于区分列表的功能,该功能利用了 LIS 算法。
问题描述 东东有两个序列A和B。...这个题是基本的动态规划问题,LIS是最长上升子序列,LCS是最长公共子序列。 求解LIS就是设dp[i]为以当前元素结尾的最长上升序列,那么dp[i]=max(dp[j]∣j<i&&a
最长上升子序列问题可以这样定义:给定一个无序的整数数组,任务是找到该数组中一个最长的子序列,使得这个子序列中的元素从左到右是严格递增的。这里的“子序列”是指从原数组中挑选出的一些元素,它们保持原序列中...
探讨了生物信息挖掘中ó模式子序列问题的一个特例,即最长递增子序列(LIS)问题。对于LIS问题,分别用LCS算法、动态规划、动态规划结合二分法进行求解,并分析了这三种算法的时间和空间复杂度,对其中两种算法进行了...
最长递增子序列 使序列排序的最小删除次数 经典的 LIS 问题。 找到序列的 LIS 和deletions = arr.length - LIS.length (非常类似于双调序列) 选择最后一个操作的所有可能间隔中的所有可能削减 在这里解释—— ...
校门外的树、字符串子序列、6种排序算法分析、最长递增子序列,算法分析
最长递增子序列 MaxLength: 无环有向图最长加权路径 LPS: 最长回文子序列 Knapspack: 01背包问题 ####贪心算法 ActiveSelect: 活动选择问题 IGCP: 区间染色问题 ####图算法 ListGraph: 邻接链表表示法 Transpose: ...
描述:给定一个未排序的整数数组,找出最长递增子序列的长度。 给定一个未排序的整数数组,找出最长递增子序列的长度。 class Solution: def lengthOfLIS(self, nums: List[int]) -> int: N = len(nums) # Recursive...
数组中最长的递增子序列在最长增加子序列(LIS)问题中,找到给定序列的最长子序列的长度,以使该子序列的所有元素都按升序排序 Ex: Input : arr[] = {3, 10, 2, 1, 20,4,56,78,90} Output : Length of LIS = 6 ...
leetcode刷题app 面试 Google 招聘的网上算法试场,一般一场打进前40可能会收到Google的面试邀约 ...最长递增子序列 - LIS(Longest Increasing Subsequence) 2.3 01背包 - 01 Knapsack 3. 数据结构 3.1 二叉搜索树