LeetCode152- 乘积最大子数组 -medium

书旅

关注

发布于: 2020 年 08 月 21 日

>标签：动态规划

题目：乘积最大子数组

题号：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;    }}