`

【串和序列处理 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<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)。

 

分享到:
评论

相关推荐

    最长递增子序列问题

    最长递增子序列(Longest Increasing Subsequence, LIS)问题是计算机科学中的一种经典动态规划问题,广泛应用于算法设计和分析。在给定的整数序列中,我们的目标是找到一个尽可能长的、不降序的子序列。这个子序列...

    动态规划:最长单调递增子序列

    本篇文章将详细介绍如何利用动态规划求解一个经典问题——寻找给定序列中的最长单调递增子序列(Longest Increasing Subsequence, LIS)。 #### 问题描述 假设有一个整数序列 `a1, a2, ..., aN`。如果存在一个序列...

    最长子序列什么是最长递增子序列呢

    最长递增子序列 (Longest Increasing Subsequence, LIS) 是指在这个序列中找到的一个子序列 \( L_{\text{in}} = \langle a_{k_1}, a_{k_2}, \ldots, a_{k_m} \rangle \),满足以下两个条件: 1. 序列中的下标满足 \...

    LIS最长单调递增子序列

    在LIS问题中,我们可以定义一个dp数组,其中dp[i]表示以序列中的第i个元素结尾的最长递增子序列的长度。通过遍历整个序列,我们可以更新dp数组,从而得到最终的LIS长度。 以下是解决LIS问题的基本步骤: 1. 初始化...

    最长递增子序列java源码

    在本实验中,我们将探讨如何使用Java编程语言解决“最长递增子序列”(Longest Increasing Subsequence, LIS)的问题。这是一个经典的动态规划问题,在计算机科学和算法设计中具有广泛的应用,例如在股票交易策略、...

    最长递增子序列 动态规划法.cpp.rar

    最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中常见的算法问题,它在数组或序列中寻找一个尽可能长的严格递增子序列。这个问题在多种领域都有应用,比如股票交易策略、生物信息学等。在这个...

    中科大算法导论课程实验 最长递增子序列 报告

    在中科大软件学院开设的算法导论课程实验中,要求学生研究和实现最长递增子序列问题。最长递增子序列(Longest Increasing Subsequence,简称LIS)问题是一个经典的计算机科学问题,其目标是在一个无序的整数序列中...

    最长递增子序列多种实现(java)

    最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中一种经典的动态规划问题,广泛应用于算法竞赛和实际编程场景。在这个Java实现中,我们将深入探讨如何找到一个序列中长度最长的递增子序列。 ...

    中科大算法导论课程实验 最长递增子序列 代码

    在本实验中,我们关注的是“最长递增子序列”(Longest Increasing Subsequence, LIS)这一经典问题,它是算法课程中的一个核心课题,尤其在动态规划的应用上有着重要的地位。中科大软件学院的这个实验旨在让学生...

    最长递增子序列LCS的实现C源码

    最长递增子序列(Longest Increasing Subsequence, LCS)是计算机科学中一种经典的动态规划问题,常见于算法和数据结构的学习。在这个问题中,我们给定一个无序整数序列,目标是找到序列中的一个子序列,使得这个子...

    LIS 最长递增子序列 Java的简单实现

    最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中的一种经典问题,它在数组或序列中寻找一个尽可能长的递增子序列。这个问题具有多种应用,如在股票交易策略、优化调度和生物信息学等领域都...

    最长递增子序列C程序

    最长递增子序列(Longest Increasing Subsequence, LIS)问题是一个经典的计算机科学问题,它在动态规划、算法设计和序列分析等领域都有广泛的应用。在这个C程序中,我们将深入探讨如何利用C语言来解决这个问题。 ...

    排序最长递增子序列红黑树

    标题中的“排序最长递增子序列红黑树”是指在数据结构和算法领域中的两个重要概念:排序和最长递增子序列(Longest Increasing Subsequence, LIS),以及它们与红黑树(Red-Black Tree)的关联。在这个场景中,我们...

    求取最长递增子序列(MFC编程)

    最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中一个经典的算法问题,主要涉及到了排序、数组处理和优化策略等概念。在这个场景中,我们将关注使用贪心算法和动态规划来解决这个问题,并结合...

    最长递增子序列的另外一种C语言实现代码

    最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中的一种经典算法问题,主要出现在算法设计与分析的课程中。这个问题的目标是从给定的一组整数中找到一个尽可能长的严格递增的子序列。在本例中...

    求一个整数序列的最长递增子序列.doc

    最长递增子序列(Longest Increasing Subsequence,简称LIS)是计算机科学中的一个重要问题,特别是在算法设计和分析中。它要求找到一个给定序列中的一个子序列,使得这个子序列是递增的,并且长度最长。 在给定的...

    js代码-求最长递增子序列

    在JavaScript编程中,"求最长递增子序列"(Longest Increasing Subsequence,LIS)是一个经典的动态规划问题。该问题旨在找到一个数组中的最长子序列,使得子序列中的元素顺序是递增的,但子序列不必是连续的。这个...

    最长递增子序列1

    最长递增子序列(LIS)是数组或序列中一个重要的概念,它的目标是找到一个序列的最长子序列,使得这个子序列中的元素是严格递增的。在给定的描述中,我们看到了三种不同的方法来求解LIS问题。 **方法一:动态规划...

    算法实验(整数划分、各类排序、最长递增子序列、幻方矩阵)

    3. 最长递增子序列(LIS): 这是一个经典的动态规划问题,目标是找到一个序列的最长子序列,使得子序列中的每个元素都小于其后的元素。LIS问题在许多实际应用中都有所体现,如股票投资决策、比赛排名等。解决LIS...

Global site tag (gtag.js) - Google Analytics