当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

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

发表于: 2012-10-07   作者:128kj   来源:转载   浏览:
摘要: 最长单调递增子序列的长度问题   所谓子序列,就是在原序列里删掉若干个元素后剩下的序列,以字符串"abcdefg"为例子,去掉bde得到子序列"acfg",。现在的问题是,给你一个数字序列,你要求出它最长的单调递增子序列的长度(LIS)。   设给定序列为 array[],大小为 n, 最长单调子序列必定以序列array[]中的某
最长单调递增子序列的长度问题
  所谓子序列,就是在原序列里删掉若干个元素后剩下的序列,以字符串"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

下载:

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1、最优二叉搜索树的动态规则算法 二叉搜索树是一颗满足如下条件的树: 1.每个节点包含一个键值 2.每
一、数组的最大子段和问题: 给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列
凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1,v2,… ,v8},任意两顶点间的线段的权重由矩阵
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解
例一:计算二项式系数: 在排列组合里面,我们有下面的式子(很容易用组合的定义来证明): 这个式
例一: 给出N台电脑和K辆卡车,要求每辆卡车至少放一台电脑。问共有多少种放法运走这些电脑? 数据范
1,什么是动态规划(DP)? 非常重要!,不要认为概念不重要,理解的深刻,你才知道对于什么样的问
前言 最近帮同学写一个程序,给出100多个金额,用数组表示为money[1-100],再给出一个数额SUM。如果
动态规划方法是对解最优问题的一种方法,一种途径,并不是一种特殊的算法。 执行步骤: 1. 找出最优
《Java与模式》学习笔记之九-----策略模式(Strategy Pattern) 收藏 策略模式是对算法的包装,把使
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号