小工具知识网

当前位置: 首页 > 行业知识 > 动态规划课堂4-----子数组系列

行业知识

动态规划课堂4-----子数组系列

2026-11-16 10:09:57 来源:互联网转载

���录

引入:

例题1:最大子数组和

例题2:环形子数组的最大和

例题3:乘积最大子数组

例题4:乘积为正数的最长子数组

总结:

结语:


引入:

在动态规划(DP)子数组系列中,我们还是用前面几节所用的解题思路1. 状态表示,2.状态转移方程,3.初始化,4.填表顺序,5.返回值。在写代码时一定要把这5步考虑清楚再写代码。写代码时其步骤也比较固定分别为:1.创建 dp 表 2.初始化 3.填表 4.返回值。写代码时可以按照这4步骤写不会乱也不会把哪一部分漏掉。

在子数组系列问题最常用到的状态表示是:以i位置元素为结尾的所有子数组的........(题目要求).

这个非常重要,后面的题基本都是用这个模板的状态表示。

例如下图:可以将其分为两种情况长度为1和长度大于1两种情况,剩下的分析要见具体题目。

例题1:最大子数组和

链接:最大子数组和

题目简介:

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

子数组:

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

解法(动态规划):

 1. 状态表示:

dp[i] 表示:以i 位置元素为结尾的「所有⼦数组」中和的最⼤和。设个状态表示会贯穿我们这一整个系列。

 2.状态转移方程

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

(1)子数组的⻓度为1 :此时dp[i] = nums[i] ;(就只有它本身)

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

由于我们要的是「最⼤值」,因此应该是两种情况下的最⼤值,因此可得转移⽅程: dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。

 3.初始化:

辅助结点法:

注意点:(1)辅助结点⾥⾯的值要保证后续填表是正确的.(2)下标的映射关系.

在本题中,最前⾯加上⼀个格⼦,并且让dp[0] = 0 即可。之所以设为0是因为根据1.状态表示,0位置没有元素(因为dp表加了一个辅助节点故dp表的0下标对应数组的-1下标),而我们的dp里面的值是最大和,没有数组故其和为0.

 4.填表顺序:

从左往右

 5.返回值:

状态表示为以i 为结尾的所有⼦数组的最⼤值,但是最⼤⼦数组和的结尾我们是不确定的(可能前面很大最后一个数非常小导致其不是最大值)。 因此我们需要返回整个dp 表中的最大值。

代码实现如下:

class Solution {    public int maxSubArray(int[] nums) {        //1.创建 dp 表        //2.初始化        //3.填表        //4.返回值        int n = nums.length;        int[] dp = new int[n + 1];        for(int i = 1;i 

上一篇:易语言实现账号密码安全存储秘籍,教程带你轻松掌握!

下一篇:抖音直播网页版全新上线,在线观看直播的极致体验