【算法优选】 动态规划之子数组、子串系列——壹

2024-05-14 21:04

本文主要是介绍【算法优选】 动态规划之子数组、子串系列——壹,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 🎋前言
  • 🎋最大子数组和
    • 🚩题目描述
    • 🚩算法思路
    • 🚩代码实现
  • 🌴环形子数组的最大和
    • 🚩题目描述
    • 🚩算法思路:
    • 🚩代码实现
  • 🌲乘积最大子数组
    • 🚩题目描述
    • 🚩算法思路:
    • 🚩代码实现
  • ⭕总结

🎋前言

动态规划相关题目都可以参考以下五个步骤进行解答:

  1. 状态表示

  2. 状态转移⽅程

  3. 初始化

  4. 填表顺序

  5. 返回值

后面题的解答思路也将按照这五个步骤进行讲解。

🎋最大子数组和

🚩题目描述

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组是数组中的一个连续部分。

  • 示例 1:
    输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出:6
    解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
  • 示例 2:
    输入:nums = [1]
    输出:1
  • 示例 3:
    输入:nums = [5,4,-1,7,8]
    输出:23
class Solution {public int maxSubArray(int[] nums) {}
}

🚩算法思路

  1. 状态表示:

对于线性 dp ,我们可以⽤「经验 + 题⽬要求」来定义状态表示:

  • 以某个位置为结尾,进行一系列操作;
  • 以某个位置为起点,进行一系列操作。

这⾥我们选择比较常用的方式,以「某个位置为结尾」,结合「题目要求」,定义⼀个状态表示:

dp[i] 表⽰:以 i 位置元素为结尾的「所有⼦数组」中和的最⼤和。

  1. 状态转移⽅程:

dp[i] 的所有可能可以分为以下两种:

  • 子数组的长度为 1 :此时 dp[i] = nums[i] ;
  • 子数组的长度⼤大于 1 :此时 dp[i] 应该等于 以 i - 1 做结尾的「所有⼦数组」中和 的最⼤值再加上 nums[i] ,也就是 dp[i - 1] + nums[i] 。

由于我们要的是「最大值」,因此应该是两种情况下的最⼤值,因此可得转移⽅程:

  • dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。
  1. 初始化:

可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使用这种技巧要注意两个点:

  • 辅助结点里面的值要「保证后续填表是正确的」;
  • 「下标的映射关系」。

在本题中,最前⾯加上⼀个格⼦,并且让 dp[0] = 0 即可。

  1. 填表顺序

根据「状态转移⽅程」易得,填表顺序为「从左往右」。

  1. 返回值:

状态表示为「以 i 为结尾的所有⼦数组」的最⼤值,但是最大子数组和的结尾我们是不确定的。

因此我们需要返回整个 dp 表中的最⼤值。

🚩代码实现

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length + 1];int ret = Integer.MIN_VALUE;for (int  i = 1; i < dp.length; i++) {dp[i] = Math.max(nums[i -1],dp[i - 1] + nums[i - 1]);ret = Math.max(ret,dp[i]);}return ret;}
}

在这里插入图片描述

🌴环形子数组的最大和

🚩题目描述

给定一个长度为 n 的环形整数数组 nums ,返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i + 1) % n] , nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上,对于子数组 nums[i], nums[i + 1], …, nums[j] ,不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

  • 示例 1:
    输入:nums = [1,-2,3,-2]
    输出:3
    解释:从子数组 [3] 得到最大和 3
  • 示例 2:
    输入:nums = [5,-3,5]
    输出:10
    解释:从子数组 [5,5] 得到最大和 5 + 5 = 10
  • 示例 3:
    输入:nums = [3,-2,2,-3]
    输出:3
    解释:从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
class Solution {public int maxSubarraySumCircular(int[] nums) {}
}

🚩算法思路:

本题与「最大子数组和」的区别在于,考虑问题的时候不仅要分析「数组内的连续区域」,还要考虑「数组⾸尾相连」的⼀部分。结果的可能情况分为以下两种:

  1. 结果在数组的内部,包括整个数组;
  2. 结果在数组首尾相连的⼀部分上。

其中,对于第⼀种情况,我们仅需按照「最大子数组和」的求法就可以得到结果,记为 fmax 。

对于第⼆种情况,我们可以分析⼀下:

  • 如果数组⾸尾相连的⼀部分是最⼤的数组和,那么数组中间就会空出来⼀部分;
  • 因为数组的总和 sum 是不变的,那么中间连续的⼀部分的和⼀定是最小的;

因此,我们就可以得出⼀个结论,对于第⼆种情况的最⼤和,应该等于 sum - gmin ,其中gmin 表⽰数组内的「最⼩⼦数组和」。

两种情况下的最⼤值,就是我们要的结果。

但是,由于数组内有可能全部都是负数,第⼀种情况下的结果是数组内的最⼤值(是个负数),第⼆种情况下的 gmin == sum ,求的得结果就会是 0 。

若直接求两者的最⼤值,就会是 0 。但是实际的结果应该是数组内的最⼤值。对于这种情况,我们需要特殊判断⼀下。

由于「最⼤⼦数组和」的⽅法已经讲过,这⾥只提⼀下「最⼩⼦数组和」的求解过程,其实与「最⼤⼦数组和」的求法是⼀致的。⽤ f 表⽰最⼤和, g 表⽰最⼩和。

  1. 状态表示:

g[i] 表⽰:以 i 做结尾的「所有⼦数组」中和的最⼩值。

  1. 状态转移⽅程:

g[i] 的所有可能可以分为以下两种:

  1. ⼦数组的⻓度为 1 :此时 g[i] = nums[i] ;
  2. ⼦数组的⻓度⼤于 1 :此时 g[i] 应该等于 以 i - 1 做结尾的「所有⼦数组」中和的最⼩值再加上 nums[i] ,也就是 g[i - 1] + nums[i] 。

由于我们要的是最⼩⼦数组和,因此应该是两种情况下的最⼩值,因此可得转移⽅程:

  • g[i] = min(nums[i], g[i - 1] + nums[i]) 。
  1. 初始化:
    可以在最前⾯加上⼀个辅助结点,帮助我们初始化。使⽤这种技巧要注意两个点:
  • 辅助结点⾥⾯的值要保证后续填表是正确的;

  • 下标的映射关系。

在本题中,最前⾯加上⼀个格⼦,并且让 g[0] = 0 即可。

  1. 填表顺序:

根据状态转移⽅程易得,填表顺序为「从左往右」。

  1. 返回值:
  • 先找到 f 表⾥⾯的最⼤值 -> fmax ;
  • 找到 g 表⾥⾯的最⼩值 -> gmin ;
  • 统计所有元素的和 -> sum ;
  • 返回 sum == gmin ? fmax : max(fmax, sum - gmin)

🚩代码实现

    public int maxSubarraySumCircular(int[] nums) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int n = nums.length;int[] f = new int[n + 1];int[] g = new int[n + 1];int sum = 0;int fmax = Integer.MIN_VALUE;int gmin = Integer.MAX_VALUE;for(int i = 1; i <= n; i++) {int x = nums[i - 1];f[i] = Math.max(x, x + f[i - 1]);fmax = Math.max(fmax, f[i]);g[i] = Math.min(x, x + g[i - 1]);gmin = Math.min(gmin, g[i]);sum += x;}return sum == gmin ? fmax : Math.max(fmax, sum - gmin);}

在这里插入图片描述

🌲乘积最大子数组

🚩题目描述

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续

子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

  • 示例 1:
    输入: nums = [2,3,-2,4]
    输出: 6
    解释: 子数组 [2,3] 有最大乘积 6。
  • 示例 2:
    输入: nums = [-2,0,-1]
    输出: 0
    解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
class Solution {public int maxProduct(int[] nums) {}
}

🚩算法思路:

这道题与「最大子数组和] 非常相似,我们可以效仿着定义⼀下状态表⽰以及状态转移:

  • dp[i] 表示以 i 为结尾的所有子数组的最⼤乘积,
  • dp[i] = max(nums[i], dp[i - 1] * nums[i]) ;

由于正负号的存在,我们很容易就可以得到,这样求 dp[i] 的值是不正确的。因为 dp[i - 1] 的信息并不能让我们得到 dp[i] 的正确值。

比如数组 [-2, 5, -2] ,用上述状态转移得到的 dp数组为 [-2, 5, -2] ,最⼤乘积为 5 。但是实际上的最⼤乘积应该是所有数相乘,结果为 20 。

究其原因,就是因为我们在求 dp[2] 的时候,因为 nums[2] 是⼀个负数,因此我们需要的是「 i - 1 位置结尾的最⼩的乘积 (-10) 」,这样⼀个负数乘以「最⼩值」,才会得到真实的最⼤值。

因此,我们不仅需要⼀个「乘积最⼤值的 dp 表」,还需要⼀个「乘积最⼩值的 dp 表」。

  1. 状态表⽰:

f[i] 表⽰:以 i 结尾的所有⼦数组的最⼤乘积,
g[i] 表⽰:以 i 结尾的所有⼦数组的最⼩乘积。

  1. 状态转移⽅程:

遍历每⼀个位置的时候,我们要同步更新两个 dp 数组的值。

对于 f[i] ,也就是「以 i 为结尾的所有⼦数组的最⼤乘积」,对于所有⼦数组,可以分为下⾯三种形式:

  • ⼦数组的⻓度为 1 ,也就是 nums[i] ;
  • ⼦数组的⻓度⼤于 1 ,但 nums[i] > 0 ,此时需要的是 i - 1 为结尾的所有⼦数组的最⼤乘积 f[i - 1] ,再乘上 nums[i] ,也就是 nums[i] * f[i - 1] ;
  • ⼦数组的⻓度⼤于 1 ,但 nums[i] < 0 ,此时需要的是 i - 1 为结尾的所有⼦数组的最⼩乘积 g[i - 1] ,再乘上 nums[i] ,也就是 nums[i] * g[i - 1] ;(如果 nums[i] = 0 ,所有⼦数组的乘积均为 0 ,三种情况其实都包含了)

综上所述, f[i] = max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i -
1]) )。

对于 g[i] ,也就是「以 i 为结尾的所有⼦数组的最⼩乘积」,对于所有⼦数组,可以分为下⾯三种形式:

  • 子数组的⻓度为 1 ,也就是 nums[i] ;
  • 子数组的⻓度⼤于 1 ,但 nums[i] > 0 ,此时需要的是 i - 1 为结尾的所有子数组的最⼩乘积 g[i - 1] ,再乘上 nums[i] ,也就是 nums[i] * g[i - 1] ;
  • 子数组的长度度⼤于 1 ,但 nums[i] < 0 ,此时需要的是 i - 1 为结尾的所有子数组的最⼤乘积 f[i - 1] ,再乘上 nums[i] ,也就是 nums[i] * f[i - 1] ;

综上所述, g[i] = min(nums[i], min(nums[i] * f[i - 1], nums[i] * g[i - 1])) 。
(如果 nums[i] = 0 ,所有⼦数组的乘积均为 0 ,三种情况其实都包含了)

  1. 初始化:

可以在最前面加上⼀个辅助结点,帮助我们初始化。使⽤这种技巧要注意两个点:

  • 辅助结点里面的值要保证后续填表是正确的;
  • 下标的映射关系。

在本题中,最前⾯加上⼀个格⼦,并且让 f[0] = g[0] = 1 即可。

  1. 填表顺序:

根据状态转移⽅程易得,填表顺序为「从左往右,两个表⼀起填」。

  1. 返回值:

返回 f 表中的最⼤值

🚩代码实现

class Solution {public int maxProduct(int[] nums) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int n = nums.length;int[] f = new int[n + 1];int[] g = new int[n + 1];f[0] = 1;g[0] = 1;int ret = Integer.MIN_VALUE;for(int i = 1; i <= n; i++) {int x = nums[i - 1];int y = f[i - 1] * nums[i - 1];int z = g[i - 1] * nums[i - 1];f[i] = Math.max(x, Math.max(y, z));g[i] = Math.min(x, Math.min(y, z));ret = Math.max(ret, f[i]);}return ret;}
}

在这里插入图片描述

⭕总结

关于《【算法优选】 动态规划之子数组、子串系列——壹》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!

这篇关于【算法优选】 动态规划之子数组、子串系列——壹的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...