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)

<?php
class 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 日 阅读数: 26
用户头像

书旅

关注

公众号:IT猿圈 2019.04.11 加入

还未添加个人简介

评论

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