动态规划求解最长递增子序列的长度

简介:

一,问题描述

给定一个序列,求解它的最长 递增 子序列 的长度。比如: arr[] = {3,1,4,1,5,9,2,6,5}   的最长递增子序列长度为4。即为:1,4,5,9

 

二,算法分析

有两种方式来求解,一种是转化为LCS问题。即,首先对数组排序,将排序后的结果存储在辅助数组中。排序时间复杂度O(NlogN),排序后的数组与原数组组成了LCS(N,N)问题。解决LCS问题的时间复杂度为O(N^2),故整个算法的时间复杂度为O(N^2),空间复杂度为O(N)

 

另一种方式是直接用DP求解,算法如下:时间复杂度为O(N^2)

①最优子问题

设lis[i] 表示索引为 [0...i] 上的数组上的 最长递增子序列。初始时,lis[i]=1,注意,在DP中,初始值是很重要的,它是整个算法运行正确的关键而初始值 则可以 通过 画一个小的示例来 确定。

当 arr[i] > arr[j],lis[i] = max{lis[j]}+1 ;其中,j 的取值范围为:0,1...i-1

当 arr[i] < arr[j],lis[i] = max{lis[j]} ;其中,j 的取值范围为:0,1...i-1

 

②重叠子结构

从上面可以看出,计算 lis[i]时,需要计算 lis[j],其中 j < i,这说明有重叠子问题。借用网路中一张图如下:

复制代码
                     lis(4)           
                 /       |      \
         lis(3)      lis(2)    lis(1)  
        /     \        /         
  lis(2)  lis(1)   lis(1) 
  /    
lis(1)
复制代码

而初始值 则可以 通过 画一个小的示例来 确定。

 

参考资料:

求解两个字符串的最长公共子序列

动态规划(3)-最长递增子序列

 

三,代码实现

错误版本1:

复制代码
 1     private static int lis(int[] arr, int length){
 2         int lis[] = new int[length];
 3         
 4         //init
 5         for(int i = 0; i < length; i++)
 6             lis[i] = 1;
 7         
 8         for(int i = 1; i < length; i++)
 9         {
10             for(int j = 0; j < i; j++)
11             {
12                 
13                 if(arr[i] > arr[j])
14                 {
15                     if(lis[j] + 1 > lis[i])
16                         lis[i] = lis[j] + 1;
17                 }
18                 else{
19                     if(lis[j] > lis[i])
20                         lis[i] = lis[j];
21                 }
22             }
23         }
24         return lis[length - 1];
25     }
复制代码

第13行if语句会导致bug,arr[i]要大于 j belongs to  0,1,...i-1 中所有的 arr[j]中的最大值,并且 lis[i] 是该最大值 arr[j] 所对应的 lis[j] +1,而不是某个其他的arr[j] 对应的 lis[j]+1

 

正确完整版本:

复制代码
public class LIS {
    public static int lis(int[] arr){
        if(arr == null || arr.length == 0)
            return 0;
        return lis(arr, arr.length);
    }
    
    private static int lis(int[] arr, int length){
        int lis[] = new int[length];
        
        //init
        for(int i = 0; i < length; i++)
            lis[i] = 1;
        
        for(int i = 1; i < length; i++)
        {
            for(int j = 0; j < i; j++)
            {
//                lis[i]=max{lis[i-1], lis[i-1]+1}
                if(arr[i] > arr[j] && lis[j] + 1 > lis[i])
                    lis[i] = lis[j] + 1;
            }
        }
        
        int max = lis[0];
        for(int i = 1; i < length; i++)
            if(max < lis[i])
                max = lis[i];
        return max;
    }
    
    public static void main(String[] args) {
        int[] arr = {3,1,4,1,5,9,2,6,5};
        int result = lis(arr);
        System.out.println(result);
    }
}本文转自hapjin博客园博客,原文链接:http://www.cnblogs.com/hapjin/p/5597658.html,如需转载请自行联系原作者
复制代码
相关文章
|
9月前
|
算法 测试技术
【学会动态规划】最长湍流子数组(23)
【学会动态规划】最长湍流子数组(23)
29 0
|
10月前
【动态规划刷题 15】最长定差子序列&& 最长的斐波那契子序列的长度
【动态规划刷题 15】最长定差子序列&& 最长的斐波那契子序列的长度
|
10月前
【动态规划刷题 13】最长递增子序列&& 摆动序列
【动态规划刷题 13】最长递增子序列&& 摆动序列
|
10月前
|
算法 JavaScript Go
【动态规划】最长递增子序列
【动态规划】最长递增子序列
|
2月前
|
算法 程序员 索引
【算法训练-动态规划 三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离
【算法训练-动态规划 三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离
78 0
|
2月前
|
算法 程序员
【算法训练-动态规划 二】【线性DP问题】连续子数组的最大和、乘积最大子数组、最长递增子序列
【算法训练-动态规划 二】【线性DP问题】连续子数组的最大和、乘积最大子数组、最长递增子序列
76 0
|
9月前
|
算法
【学会动态规划】最长递增子序列的个数(28)
【学会动态规划】最长递增子序列的个数(28)
28 0
|
9月前
|
算法
【学会动态规划】 最长递增子序列(26)
【学会动态规划】 最长递增子序列(26)
25 0
深入理解动态规划算法 - 最长公共子序列
深入理解动态规划算法 - 最长公共子序列
59 0
|
存储 人工智能 算法
『动态规划』最长上升子序列
输入母串的长度 循环输入母串数组以及母串的状态数组并初始化 外层循环,从左往右遍历,记录待更新数组为a[i] 里层循环,遍历母串的左闭右开区间[0,i),找到比a[i]小且状态值最大的数,更新a[i]的状态数组b[i] 用一个变量max记录状态数组b[i]的最大值就是最大子序列的数量
136 0

热门文章

最新文章