顺德营销型网站建设,网站国内服务器租用,住房和建设局官网,网络营销管理师文章目录 #x1f38b;前言#x1f38b;最大子数组和#x1f6a9;题目描述#x1f6a9;算法思路#x1f6a9;代码实现 #x1f334;环形子数组的最大和#x1f6a9;题目描述#x1f6a9;算法思路#xff1a;#x1f6a9;代码实现 #x1f332;乘积最大子数组#x… 文章目录 前言最大子数组和题目描述算法思路代码实现 环形子数组的最大和题目描述算法思路代码实现 乘积最大子数组题目描述算法思路代码实现 ⭕总结 前言
动态规划相关题目都可以参考以下五个步骤进行解答 状态表示 状态转移⽅程 初始化 填表顺序 返回值
后面题的解答思路也将按照这五个步骤进行讲解。
最大子数组和
题目描述
给你一个整数数组 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) {}
}算法思路
状态表示
对于线性 dp 我们可以⽤「经验 题⽬要求」来定义状态表示
以某个位置为结尾进行一系列操作以某个位置为起点进行一系列操作。
这⾥我们选择比较常用的方式以「某个位置为结尾」结合「题目要求」定义⼀个状态表示
dp[i] 表⽰以 i 位置元素为结尾的「所有⼦数组」中和的最⼤和。
状态转移⽅程
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]) 。
初始化
可以在最前⾯加上⼀个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点
辅助结点里面的值要「保证后续填表是正确的」「下标的映射关系」。
在本题中最前⾯加上⼀个格⼦并且让 dp[0] 0 即可。
填表顺序
根据「状态转移⽅程」易得填表顺序为「从左往右」。
返回值
状态表示为「以 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) {}
}算法思路
本题与「最大子数组和」的区别在于考虑问题的时候不仅要分析「数组内的连续区域」还要考虑「数组⾸尾相连」的⼀部分。结果的可能情况分为以下两种
结果在数组的内部包括整个数组结果在数组首尾相连的⼀部分上。
其中对于第⼀种情况我们仅需按照「最大子数组和」的求法就可以得到结果记为 fmax 。
对于第⼆种情况我们可以分析⼀下
如果数组⾸尾相连的⼀部分是最⼤的数组和那么数组中间就会空出来⼀部分因为数组的总和 sum 是不变的那么中间连续的⼀部分的和⼀定是最小的
因此我们就可以得出⼀个结论对于第⼆种情况的最⼤和应该等于 sum - gmin 其中gmin 表⽰数组内的「最⼩⼦数组和」。
两种情况下的最⼤值就是我们要的结果。
但是由于数组内有可能全部都是负数第⼀种情况下的结果是数组内的最⼤值是个负数第⼆种情况下的 gmin sum 求的得结果就会是 0 。
若直接求两者的最⼤值就会是 0 。但是实际的结果应该是数组内的最⼤值。对于这种情况我们需要特殊判断⼀下。
由于「最⼤⼦数组和」的⽅法已经讲过这⾥只提⼀下「最⼩⼦数组和」的求解过程其实与「最⼤⼦数组和」的求法是⼀致的。⽤ f 表⽰最⼤和 g 表⽰最⼩和。
状态表示
g[i] 表⽰以 i 做结尾的「所有⼦数组」中和的最⼩值。
状态转移⽅程
g[i] 的所有可能可以分为以下两种
⼦数组的⻓度为 1 此时 g[i] nums[i] ⼦数组的⻓度⼤于 1 此时 g[i] 应该等于 以 i - 1 做结尾的「所有⼦数组」中和的最⼩值再加上 nums[i] 也就是 g[i - 1] nums[i] 。
由于我们要的是最⼩⼦数组和因此应该是两种情况下的最⼩值因此可得转移⽅程
g[i] min(nums[i], g[i - 1] nums[i]) 。
初始化 可以在最前⾯加上⼀个辅助结点帮助我们初始化。使⽤这种技巧要注意两个点 辅助结点⾥⾯的值要保证后续填表是正确的 下标的映射关系。
在本题中最前⾯加上⼀个格⼦并且让 g[0] 0 即可。
填表顺序
根据状态转移⽅程易得填表顺序为「从左往右」。
返回值
先找到 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 表」。
状态表⽰
f[i] 表⽰以 i 结尾的所有⼦数组的最⼤乘积 g[i] 表⽰以 i 结尾的所有⼦数组的最⼩乘积。
状态转移⽅程
遍历每⼀个位置的时候我们要同步更新两个 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 三种情况其实都包含了
初始化
可以在最前面加上⼀个辅助结点帮助我们初始化。使⽤这种技巧要注意两个点
辅助结点里面的值要保证后续填表是正确的下标的映射关系。
在本题中最前⾯加上⼀个格⼦并且让 f[0] g[0] 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;}
}⭕总结
关于《【算法优选】 动态规划之子数组、子串系列——壹》就讲解到这儿感谢大家的支持欢迎各位留言交流以及批评指正如果文章对您有帮助或者觉得作者写的还不错可以点一下关注点赞收藏支持一下
