行业知识
动态规划课堂4-----子数组系列
���录
引入:
例题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