`
128kj
  • 浏览: 600193 次
  • 来自: ...
社区版块
存档分类
最新评论

动态规划算法学习十例之九

阅读更多
最长单调递增子序列的长度问题
  所谓子序列,就是在原序列里删掉若干个元素后剩下的序列,以字符串"abcdefg"为例子,去掉bde得到子序列"acfg",。现在的问题是,给你一个数字序列,你要求出它最长的单调递增子序列的长度(LIS)。

  设给定序列为 array[],大小为 n, 最长单调子序列必定以序列array[]中的某一个元素结尾,这是废话。

    设lis[i]为以array[i]结尾的最长单调子序列的长度,那么array[]的LIS的长度就是
max{lis[i]} (0<=i<n)

显然此问题具有最优子结构性质:
    lis[0]=1;
    lis[i+1]=max{1,lis[k]+1} (array[i+1]>array[k], k <= i)

即如果array[i+1]大于array[k],那么第i+1个元素可以接在lis[k]长的子序列后面构成一个更长的子序列。于此同时array[i+1]本身至少可以构成一个长度为1的子序列。

import java.util.Scanner;
public class TestLIS{
  private  int n;
  private int array[];
  private int lis[];

   public TestLIS(int n,int[] array){
      this.n=n;
      this.array=array;
      lis=new int[n];
   }

   public static void main(String[] args) { 
     
        Scanner in=new Scanner(System.in); 
        
           int n=in.nextInt(); 
           int[] array=new int[n]; 
           for(int i=0;i<n;i++){
                array[i]=in.nextInt(); 
           }  
         
          TestLIS tl=new TestLIS(n,array);
          int maxl=tl.lis();
          
          System.out.println("最长单调递增子序列长度:"+maxl); 
          System.out.println();
          System.out.println("最长单调递增子序列构成");
          int k=tl.max();
          tl.print(k);
          System.out.println();
      
       
   }
  //求数组最长递增子序列
  public  int lis()
  {
	for(int i =0;i< n;i++)
	{
		lis[i]=1;
		for(int j=0;j< i;j++)
		{
			if(array[j]< array[i]&&(lis[j]+1>lis[i]))
			  lis[i]=lis[j]+1;
                       
                
		}
               
	}
	int max=0;
	for(int k=0;k< lis.length;k++)
	{
   		if(lis[k]>max)
		max=lis[k];
	}
  	return max;
   }

 //求数组中最大值下标  
    private int max()  
    {  
        int max = lis[0];  
        int k = 0;  
        for (int i = 0; i < lis.length; i++)  
        {  
            if (max < lis[i])  
            {  
                max = lis[i];  
                k = i;  
            }  
        }  
        return k;  
    }  

     //输出   
    public void print(int k)  
    {      
        for (int i = k - 1; i >= 0; i--)  
        {  
            if (lis[k] == lis[i] + 1 && array[i] <= array[k])  
            {  
                print(i);  
                break;  
            }  
        }  
        System.out.print(array[k] + " ");  
    }  

 }


运行:
5
1 10 4 9 7
最长单调递增子序列长度:3

最长单调递增子序列构成
1 4 9

下载:
分享到:
评论

相关推荐

    动态规划算法学习十例之八

    标题 "动态规划算法学习十例之八" 暗示了我们将探讨动态规划这一重要的算法概念,特别是通过一个具体的例子——Matrix Chain Multiplication(矩阵链乘法)来深入理解。动态规划是一种解决复杂问题的有效方法,它...

    动态规划算法学习十例之七

    在这个“动态规划算法学习十例之七”的主题中,我们将聚焦于一个具体的动态规划问题——最长公共子序列(Longest Common Subsequence,简称LCS)。这个问题在计算机科学中具有很高的实用价值,尤其是在比较和分析...

    动态规划算法学习十例之六

    在这个主题“动态规划算法学习十例之六”中,我们将探讨如何利用动态规划方法来解决实际问题。博文链接虽然未提供具体内容,但我们可以根据提供的文件名推测讨论的是一个具体的编程实例。 `Main.java`通常是一个...

    动态规划算法学习十例之五

    标题中的“动态规划算法学习十例之五”表明这篇内容主要关注的是计算机科学中的动态规划算法,这是一种在解决复杂问题时非常有效的优化方法。动态规划通常用于处理具有重叠子问题和最优子结构的问题,通过将大问题...

    动态规划算法学习十例之四

    在这个“动态规划算法学习十例之四”的主题中,我们将专注于背包问题的解决方案。背包问题是一个经典的计算机科学问题,它通常涉及在给定容量的背包中选择物品以最大化总价值。 首先,我们来了解动态规划的基本思想...

    动态规划算法学习十例之二

    在这个"动态规划算法学习十例之二"中,我们很可能会探讨两个具体的动态规划应用:一个可能涉及二项式系数计算,另一个可能是斐波那契数列的求解。下面,我们将深入这两个主题,理解它们背后的动态规划策略。 首先,...

    动态规划算法学习十例之一

    在这个“动态规划算法学习十例之一”的主题中,我们将会探讨动态规划的基本概念和一个具体的实例,通过分析`Test.java`源码来深入理解。 首先,动态规划的核心思想是将一个大问题分解为相互重叠的小问题,并通过...

    动态规划算法学习十例之三

    动态规划是一种重要的算法思想,广泛应用于解决复杂问题的优化,如最短路径、背包问题、最长公共子序列等。在本篇文章中,我们将探讨动态规划的精髓,并通过具体实例进行深入学习。博客链接提供了详细的解析,虽然...

    近似串匹配的动态规划算法

    在压缩包中的"近似串匹配问题"文件可能包含了这样的C语言实现,可以作为学习和理解近似串匹配动态规划算法的一个实例。 总结一下,近似串匹配的动态规划算法是一种高效的方法,通过Levenshtein距离或Hamming距离...

    国际大学生程序设计竞赛例题解.三:图论、动态规划算法、综合题专集

    三:图论、动态规划算法、综合题专集》是一本专门针对编程竞赛中的重要算法与问题解决策略的书籍。它涵盖了图论、动态规划以及综合题型,这些都是在竞赛中经常遇到并且至关重要的主题。下面将对这三个方面进行详细的...

    基于Python语言的“算法分析”课程设计——以动态规划算法为例.pdf

    在课程设计过程中,学生还将学习如何分析动态规划算法的时间复杂度和空间复杂度。例如,大多数动态规划解决方案的时间复杂度为O(n*W),其中n是物品数量,W是背包容量,而空间复杂度通常是O(n*W)或者更优,取决于是否...

    动态规划算法.

    在实际编程中,理解和掌握动态规划算法对于提高问题解决能力至关重要,因为它能够优雅地处理复杂度高且具有结构重叠的优化问题。在学习动态规划时,推荐阅读如《Introduction to Algorithms》等经典教材,它们深入浅...

    算法参考资料国际大学生程序设计竞赛例题解3图论·动态规划算法·综合题专集

    标题中提到的是“算法参考资料国际大学生程序设计竞赛例题解3 图论·动态规划算法·综合题专集”。这份资料集中的标题揭示了内容的几个关键点,即它是一份专门为解决算法问题而编写的参考资料,特别针对国际大学生...

    算法动态规划 专题 算法动态规划 专题 ppt

    **算法动态规划专题** 动态规划(Dynamic Programming,简称DP)是一种在计算机科学中解决最优化问题的算法技术,尤其在解决复杂度较高的多阶段决策问题时表现得尤为出色。它通过将大问题分解为小问题,并存储子...

    初识动态规划算法doc

    动态规划算法是一种强大的工具,常用于解决多阶段决策过程中的最优化问题。它通过将复杂问题分解成相互关联的子问题来求解,避免了贪婪算法或分治算法可能遇到的局限。动态规划的核心思想是备忘录法,即保存子问题的...

    学习常用算法之(7)动态规划

    动态规划算法通常包含以下几个步骤: 1. 定义状态:识别问题中的关键状态,它们通常是问题的某个阶段的特性描述。 2. 状态转移方程:建立从一个状态到下一个状态的转换规则,这个方程描述了如何根据先前的状态计算...

    基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf

    "基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf" 本文研究主要集中在基于岭回归机器学习算法的项目成本预测研究,以A风景园林规划研究院规划设计项目为例。该研究的目的...

    编程语言算法100例

    本资源包含的100例算法涵盖了排序、搜索、图论、动态规划、递归等多个重要类别。 1. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。排序算法是数据处理的基础,用于将一组无序的...

Global site tag (gtag.js) - Google Analytics