动态规划 最长递增子序列

方法一:最长公共子序列法

将问题转换成求递增排序的数组与原数组的最长公共子序列。
不知道如何排序?看这里: 七大排序算法总结
不知道什么是最长公共子序列?看这里: 最长公共子序列问题总结


方法二:动态规划法

通过递推思路解决问题。要求长度为i的序列的Ai{a1,a2,……,ai}最长递增子序列,需要先求出序列Ai-1{a1,a2,……,ai-1}中以各元素(a1,a2,……,ai-1)作为最大元素的最长递增序列,然后把所有这些递增序列与ai比较,如果某个长度为m序列的末尾元素aj(j<i)比ai要小,则将元素ai加入这个递增子序列,得到一个新的长度为m+1的新序列,否则其长度不变,将处理后的所有i个序列的长度进行比较,其中最长的序列就是所求的最长递增子序列。

lis数组存储各元素作为最大元素的最长递增序列长度
pre前驱元素数组,记录当前以该元素作为最大元素的递增序列中该元素的前驱节点

import java.util.Stack;

public class test03231626 {
    
    public static int lis(int [] array)
    {
        int []lis = new int[array.length];
        int[] pre=new int[array.length];
        for(int i =0;i<array.length;i++)
        {
            lis[i]=1;
            pre[i]=i;
        }
         for (int j=1; j<array.length; j++) {  
                for (int i=0; i<j; i++) {  
                    if (array[j]>array[i] && lis[j]<lis[i]+1){ //注意array[j]<array[i]+1这个条件,不能省略。  
                        lis[j] = lis[i] + 1; //计算以array[j]结尾的序列的最长递增子序列长度  
                        pre[j]=i;
                    }  
                }  
            }  
        
        int max=0,index = 0;
        for(int k=0;k<lis.length;k++)
        {
            if(lis[k]>max){
                max=lis[k];
                index=k;
            }
        }
        System.out.println("最长递增子序列长度:"+max);
        Stack<Integer> stack=new Stack<Integer>();  
        while(index!=pre[index]){
            //System.out.print(array[index]+" ");   
            stack.push(array[index]);
            index=pre[index];       
        }

        if(index==pre[index])
        //  System.out.print(array[index]+" ");
            stack.push(array[index]);
        while(!stack.isEmpty())
            System.out.print(stack.pop()+" ");          
        return max;
    }
    
    
    public static void main(String[] args){
        int[] array={35, 36, 39, 3, 15, 27, 6, 42};
        lis(array);
    }
    
}
运行结果
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 问题定义: 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度...
    miltonsun阅读 1,093评论 0 1
  • 1 概述 前面的课程中讲到了图的基本遍历算法和简单的应用,本来想接着往后面继续讲,后来有童鞋说讲讲动态规划吧,看书...
    CodingTech阅读 1,580评论 2 13
  • 对于下面一个序列: 2,1,5,3,6,4,8,9,7 求其最长递增子序列(可以不连续但顺序不可变) 解法一:动态...
    LamyGoGoGo阅读 1,236评论 0 0
  • 定义一组子问题,按照由小到大,以小问题的解答支持大问题求解的模式,依次解决所有的子问题,并最终得到原问题的解答。 ...
    芥丶未央阅读 920评论 0 2
  • 原文在这里 http://blog.csdn.net/dq_dm/article/details/45043689...
    superczb阅读 1,219评论 0 1