关于最长递增子序列问题概述

2025-02-15 05:50

本文主要是介绍关于最长递增子序列问题概述,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效...

一、最长递增子序列问题概述

1. 问题定义

给定一个整数序列,例如 nums = [10, 9, 2, 5, 3, 7, 101, 18],要找出它的一个最长的子序列,使得这个子序列中的元素是严格递增的。

在上述例子中,最长递增子序列是 [2, 3, 7, 101] 或者 [2, 5, 7, 101] 等,长度为 4。

2. 常规动态规划解法思路及缺点

思路

  • 通常可以定义一个 dp 数组,其中 dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度。
  • 状态转移方程一般为 dp[rPEbRpAi] = max(dp[j]) + 1(其中 0 <= j < inums[j] < nums[i]),也就是遍历前面所有小于 nums[i] 的元素对应的 dp 值,取最大的那个再加 1 来更新 dp[i]
  • 最后整个序列的最长递增子序列长度就是 dp 数组中的最大值。

缺点

  • 这种常规解法的时间复杂度是 ,当输入序列长度 n 较大时,效率会比较低
  • 所以需要进行优化来降低时间复杂度,提升求解效率

二、优化解法一:贪心 + 二分查找(时间复杂度优化至nlogn )

1. 贪心思想

维护一个数组 tail,它用来存储当前找到的最长递增子序列的 “尾巴” 元素,这个数组的长度其实就代表了当前找到的最长递增子序列的长度(初始时长度为 0)。

对于新遍历到的元素 nums[i],我们希望以一种贪心的策略把它尽可能合理地添加到 tail 数组中,使得 tail 数组始终保持一种有序的状态(因为递增子序列的特性决定了 “尾巴” 元素是有序递增的),这样就能通过后续的操作高效地找到最长递增子序列。

2. 二分查找的运用

每当遍历到一个新元素 nums[i] 时,我们在 tail 数组中通过二分查找找到第一个大于等于 nums[i] 的元素位置 pos(可以利用 Java 中的 Arrays.binarySearch 等二分查找相关方法实现,若没找到则返回插入点,即合适的位置)。

  • 如果 pos 等于 tail 数组当前长度,说明 nums[i] 比当前所有的 “尾巴” 元素都大,那它就可以作为新的 “尾巴” 元素添加到 tail 数组末尾,使得最长递增子序列长度加 1,即 tail = Arrays.copyOf(tail, tail.length + 1); tail[tail.length - 1] = nums[i];
  • 如果 pos 小于 tail 数组当前长度,说明 nums[i] 可以替换掉 tail[pos],因为这样做不会破坏递增子序列的性质,而且有可能在后续找到更长的递增子序列,即 tail[pos] = nums[i];

3. Java 代码示例

import java.util.Arrays;

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        int[] tail = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int pos = Arrays.binarySearch(tail, 0, len, num);
            if (pos < 0) {
                pos = -(pos + 1);
            }
            tail[pos] = num;
            if (pos == len) {
                len++;
            }
        }
        return len;
    }

    public static void main(String[] args) {
China编程        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int result = lengthOfLIS(nums);
        System.out.println("最长递增子序列长度为: " + result);
    }
}

在上述代码中:

  • lengthOfphpLIS 方法实现了优化后的最长递增子序列求解逻辑。通过不断遍历输入数组 nums,利用二分查找在 tail 数组中定位合适位置来更新 tail 数组,同时维护最长递增子序列的长度 len
  • main 方法进行简单测试,传入示例数组并输出最终计算得到的最长递增子序列长度。

三、优化解法二:动态规划 + 状态压缩(时间复杂度仍为O(n^2) ,但空间复杂度优化)

1. 思路

原始动态规划解法中我们使用了一个 dp 数组来记录以每个元素为结尾的最长递增子序列长度,但是其实在计算 dp[i] 时,我们只需要知道前面元素中小于 nums[i] 的那些元素对应的 dp 值情况,并不需要把所有之前元素对应的 dp 值都完整保存下来。

所以可以通过状态压缩,只使用一个长度为 n 的一维数组来模拟动态规划过程,每次更新当前元素对应的 dp 值时,及时覆盖之前不再需要的值,从而节省空间。

2. Java 代码示例

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int result = lengthOfLIS(nums);
        System.out.println("最长递增子序列长度为: " + result);
    }
}

在这个代码示例中:

  • lengthOfLIS 方法里,通过一个一维的 dp 数组来进行动态规划求解,内层循环中不断更新 dp[i] 的值,并且实时维护最大的最长递编程增子序android列长度 maxLen,最后返回 maxLen 作为结果。
  • main 方法同样是用于简单的测试场景,展示如何调用 lengthOfLIS 方法并输出结果。

通过这些优化解法,可以更高效地解决最长递增子序列问题,在不同的应用场景和数据规模下根据实际需求选择合适的优化方式来提升算法性能。

总结

以上为个人经验,希望能给大家一个参考,也希望大家多多支持China编程(www.chinasem.cn)。

这篇关于关于最长递增子序列问题概述的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1153447

相关文章

MyBatis模糊查询报错:ParserException: not supported.pos 问题解决

《MyBatis模糊查询报错:ParserException:notsupported.pos问题解决》本文主要介绍了MyBatis模糊查询报错:ParserException:notsuppo... 目录问题描述问题根源错误SQL解析逻辑深层原因分析三种解决方案方案一:使用CONCAT函数(推荐)方案二:

Redis 热 key 和大 key 问题小结

《Redis热key和大key问题小结》:本文主要介绍Redis热key和大key问题小结,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、什么是 Redis 热 key?热 key(Hot Key)定义: 热 key 常见表现:热 key 的风险:二、

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》:本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1:创建 Maven Web 项目步骤 2:添加 Spring MVC 依赖1、保存后执行2、将新的依赖

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》:本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用?循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1