首页 > 编程语言 > 详细

5.18——152. 乘积最大子数组

时间:2020-05-24 20:35:39      阅读:48      评论:0      收藏:0      [点我收藏+]

152. 乘积最大子数组

给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
 
 
1.解题思路
53. 最大子序和)解法一致,不同的是“负负得正”。当遍历到数组中的负数时,我们希望以它前一个位置结尾的某个段的积也是个负数,这样就可以负负得正,并且我们希望这个积尽可能「负得更多」,即尽可能小。 所以我们得到了一个结论:当前位置的最优解未必是由前一个位置的最优解转移得到的。 于是这里我们可以创建一个参照数组,它表示以第 i 个元素结尾的最小子数组的乘积。
递归式:
    MAX(i)=max(nums[i], num[i]*MAX[i-1], nums[i]*MIN[i-1])
    MIN(i)=min(nums[i], num[i]*MAX[i-1], nums[i]*MIN[i-1])
 
2.源码
技术分享图片技术分享图片

5.18——152. 乘积最大子数组

原文:https://www.cnblogs.com/xiaoqichaoren/p/12951906.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!