写点什么

LeetCode152- 乘积最大子数组 -medium

用户头像
书旅
关注
发布于: 2020 年 08 月 21 日
LeetCode152-乘积最大子数组-medium

>标签:动态规划

题目:乘积最大子数组

题号:152

题干:给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积

示例 1:

输入: [2,3,-2,4]

输出: 6

解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]

输出: 0

解释: 结果不能为 2, 因为 [-2,-1] 不是子数组


思路


  • 遍历数组时计算当前最大值,不断更新

  • 初始化当前最大值和最小值 $newMax、$newMin

  • 计算当前最大值:$newMax = max($newMax*$nums[$i], $nums[$i]);

  • 因为数字数组中可能存在负数,因此原来的最大值此时会变为最小值,相反,最小值会变成最大值,因此需要记录当前最小值:$newMin = min($newMin*$nums[$i], $nums[$i]);

  • 当元素为负数时,交换当前最大值 $newMax 和当前最小值 $newMin

  • 时间复杂度:O(n)


代码实现(语言:PHP)

<?phpclass Solution {    /**    * @param Integer[] $nums    * @return Integer    */    public function maxProduct($nums) {        $newMax = $newMin = 1;        $max = $nums[0];        for ($i = 0; $i < count($nums); $i++) {            if ($nums[$i] < 0) {                $tmp = $newMax;                $newMax = $newMin;                $newMin = $tmp;            }
$newMax = max($newMax*$nums[$i], $nums[$i]); $newMin = min($newMin*$nums[$i], $nums[$i]);
$max = max($max, $newMax); }
return $max; }}
复制代码



发布于: 2020 年 08 月 21 日阅读数: 61
用户头像

书旅

关注

公众号:IT猿圈 2019.04.11 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode152-乘积最大子数组-medium