《算法题讲解指南：动态规划算法--子数组系列》--21.乘积最大子数组，22.乘积为正数的最长子数组

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录21.乘积最大子数组题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析22.乘积为正数的最长子数组题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析结束语21.乘积最大子数组题目链接152. 乘积最大子数组 - 力扣LeetCode题目描述​题目示例​解法(动态规划)算法思路这道题与「最大子数组和」非常相似我们可以效仿着定义一下状态表示以及状态转移i.dp[i]表示以i为结尾的所有子数组的最大乘积ii. dp[i] max(nums[i], dp[i - 1] * nums[i]);由于正负号的存在我们很容易就可以得到这样求dp[i]的值是不正确的。因为dp[i-1]的信息并不能让我们得到dp[i]的正确值。比如数组[-25-2]用上述状态转移得到的dp数组为[-25-2]最大乘积为5 。但是实际上的最大乘积应该是所有数相乘结果为20。究其原因就是因为我们在求dp[2]的时候因为nums[2]是一个负数因此我们需要的是「i -1 位置结尾的最小的乘积(-10)」这样一个负数乘以「最小值」才会得到真实的最大值。因此我们不仅需要一个「乘积最大值的dp表」还需要一个「乘积最小值的dp表」。1.状态表示f[i]表示:以i结尾的所有子数组的最大乘积g[i]表示:以i结尾的所有子数组的最小乘积。2.状态转移方程遍历每一个位置的时候我们要同步更新两个dp 数组的值。对于f[i]也就是「以为结尾的所有子数组的最大乘积」对于所有子数组可以分为下面三种形式i.子数组的长度为1也就是nums[i];ii.子数组的长度大于1 但nums[i]0此时需要的是i-1 为结尾的所有子数组的最大乘积f[i-1]再乘上nums[i]也就是nums[i]* f[i- 1];iii.子数组的长度大于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为结尾的所有子数组的最小乘积」对于所有子数组可以分为下面三种形式i.子数组的长度为1也就是nums[i];ii.子数组的长度大于1但nums[i]0此时需要的是i-1为结尾的所有子数组的最小乘积g[i-1]再乘上nums[i]也就是nums[i]* g[i-1];iii.子数组的长度大于1 但nums[i]0 此时需要的是i1 为结尾的所有子数组的最大乘积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三种情况其实都包含了)3.初始化可以在最前面加上一个辅助结点帮助我们初始化。使用这种技巧要注意两个点:i.辅助结点里面的值要保证后续填表是正确的;ii.下标的映射关系。在本题中最前面加上一个格子并且让f[0]g[0]1即可。4.填表顺序根据状态转移方程易得填表顺序为「从左往右两个表一起填」。5.返回值返回 f 表中的最大值。C算法代码class Solution { public: int maxProduct(vectorint nums) { int n nums.size(); vectorint max_dp(n); vectorint min_dp(n); max_dp[0] min_dp[0] nums[0]; for(int i 1; i n; i) { if(nums[i] 0) { max_dp[i] max(max_dp[i - 1] * nums[i], nums[i]); min_dp[i] min(min_dp[i - 1] * nums[i], nums[i]); } else { max_dp[i] max(min_dp[i - 1] * nums[i], nums[i]); min_dp[i] min(max_dp[i - 1] * nums[i], nums[i]); } } int ret INT_MIN; for(int i 0; i n; i) { ret max(ret, max_dp[i]); } return ret; } };算法总结及流程解析22.乘积为正数的最长子数组题目链接1567. 乘积为正数的最长子数组长度 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路继续效仿「最大子数组和」中的状态表示尝试解决这个问题。状态表示dp[i]表示「所有以i 结尾的子数组乘积为正数的最长子数组的长度」。思考状态转移:对于i位置上的nums[i]我们可以分三种情况讨论i.如果nums[i]0那么所有以i为结尾的子数组的乘积都不可能是正数此时dp[i]0;ii.如果nums[i]0 那么直接找到dp[i-1]的值(这里请再读一遍dp[i-1]代表的意义并且考虑如果dp[i-1]的结值是0 的话影不影响结果)然后加1即可此时dp[i]dp[i-1]1;iii.如果nums[i]0这时候你该蛋疼了因为在现有的条件下你根本没办法得到此时的最长长度。因为乘法是存在「负负得正」的单单靠一个dp[i-1]我们无法推导出dp[i]的值。但是如果我们知道「以i-1为结尾的所有子数组乘积为负数的最长子数组的长度」neg[i-1]那么此时的dp[i]是不是就等于neg[i-1]1呢?通过上面的分析我们可以得出需要两个dp表才能推导出最终的结果。不仅需要一个「乘积为正数的最长子数组」还需要一个「乘积为负数的最长子数组」。1.状态表示f[i]表示以i结尾的所有子数组中乘积为「正数」的最长子数组的长度;g[i]表示以i结尾的所有子数组中乘积为「负数」的最长子数组的长度。2.状态转移方程遍历每一个位置的时候我们要同步更新两个dp数组的值。对于f[i]也就是以i为结尾的乘积为「正数」的最长子数组根据nums[i]的值可以分为三种情况i.nums[i]0时所有以i为结尾的子数组的乘积都不可能是正数此时f[i]0;ii. nums[i] 0时那么直接找到f[i - 1]的值(这里请再读一遍f[i-1]代表的意义并且考虑如果f[i-1]的结值是0的话影不影响结果)然后加一即可此时 f[i] f[i- 1] 1;iii. nums[i]0时此时我们要看g[i-1] 的值(这里请再读一遍 g[i-1]代表的意义。因为负负得正如果我们知道以i-1为结尾的乘积为负数的最长子数组的长度加上1即可)根据g[i-1]的值又要分两种情况1. g[i-1]0 说明以i-1 为结尾的乘积为负数的最长子数组是不存在的又因为nums[i]0所以以i 结尾的乘积为正数的最长子数组也是不存在的此时f[i]0;2. g[i - 1] !0说明以i-1为结尾的乘积为负数的最长子数组是存在的又因为nums[i] 0所以以i 结尾的乘积为正数的最长子数组就等于g[i-1]1综上所述nums[i] 0时f[i] g[i-1 0 ? 0 : g[i-1] 1对于g[i]也就是以i为结尾的乘积为「负数」的最长子数组根据nums[i]的值可以分为三种情况i.nums[i]时所有以i为结尾的子数组的乘积都不可能是负数此时g[i]0;ii.nums[i] 0时那么直接找到f[i-1]的值(这里请再读一遍f[i-1]代表的意义并且考虑如果f[i-1]的结值是的话影不影响结果)然后加一即可(因为正数*负数负数)此时 g[i] f[i -1] 1 ;iii.nums[i]0 时此时我们要看g[i-1]的值(这里请再读一遍 g[i -1]代表的意义。因为正数*负数负数)根据g[i-1]的值又要分两种情况1.g[i- 1] 说明以i- 1 为结尾的乘积为负数的最长子数组是不存在的又因为nums[i]0所以以i结尾的乘积为负数的最长子数组也是不存在的此时f[i]0;2. g[i-1] ! 0 说明以i-1 为结尾的乘积为负数的最长子数组是存在的又因为nums[i]0所以以i 结尾的乘积为正数的最长子数组就等于g[i-1] 1;综上所述 nums[i] 0 时, g[i] g[i -1 0 ? 0 : g[i - 1] 1 ;这里的推导比较绕因为不断的出现「正数和负数」的分情况讨论我们只需根据下面的规则严格找到此状态下需要的dp 数组即可i.正数* 正数正数ii.负数*负数正数iii.负数*正数正数*负数负数3.初始化可以在最前面加上一个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点i.辅助结点里面的值要「保证后续填表是正确的」;ii. 「下标的映射关系」。在本题中最前面加上一个格子并且让f[0] g[0] 0即可。4.填表顺序根据「状态转移方程」易得填表顺序为「从左往右两个表一起填」。5.返回值根据「状态表示」我们要返回f 表中的最大值。C算法代码class Solution { public: int getMaxLen(vectorint nums) { int n nums.size(); vectorint pos_dp(n); vectorint neg_dp(n); if(nums[0] 0) { pos_dp[0] 1; neg_dp[0] 0; } else if(nums[0] 0) { pos_dp[0] 0; neg_dp[0] 1; } else { pos_dp[0] neg_dp[0] 0; } for(int i 1; i n; i) { if(nums[i] 0) { pos_dp[i] pos_dp[i - 1] 1; neg_dp[i] neg_dp[i - 1] 0 ? 0 : neg_dp[i - 1] 1; } else if(nums[i] 0) { pos_dp[i] neg_dp[i - 1] 0 ? 0 : neg_dp[i - 1] 1; neg_dp[i] pos_dp[i - 1] 1; } else { pos_dp[i] neg_dp[i] 0; } } int ret INT_MIN; for(int i 0; i n; i) { ret max(ret, pos_dp[i]); } return ret; } };算法总结及流程解析结束语到此21.乘积最大子数组22.乘积为正数的最长子数组 这两道算法题就讲解完了。对于乘积最大子数组问题采用双DP数组分别记录以i结尾的最大和最小乘积通过比较当前元素、与前驱最大乘积或最小乘积的组合来递推求解对于乘积为正数的最长子数组问题同样使用双DP数组分别记录以i结尾的正数和负数乘积最长子数组长度根据当前元素正负分情况讨论状态转移。希望大家能有所收获