题目描述

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

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

输出: 6

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

示例 2:

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

输出: 0

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

力扣（LeetCode）

解题

法一：动态规划

因为存在正数和负数，所以需要有两个状态，一个保存最小值，一个保存最大值。

对数组遍历一次即可获取最大值，时间复杂度为O(n)，空间复杂度为O(1)。

动态规划迭代公式

class Solution {

    public int maxProduct(int[] nums) {

        int length = nums.length;

        int fmax = nums[0];

        int fmin = nums[0];

        int temp = nums[0];

        for (int i = 1; i < length; ++i) {

            int mx = fmax, mn = fmin;

            fmax = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));

            fmin = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));

            temp = Math.max(fmax, temp);

        }

        return temp;

    }

}

法二：循环遍历

时间复杂度为O(n)，空间复杂度为O(1)。

class Solution {

    public int maxProduct(int[] nums) {

        // 两种特殊值，负数和零

        // 遇到0相当于要分段处理了

        // 每一段中的负数个数为偶时，全部相乘

        // 每一段中的负数个数为奇时，只取左边的最大值或者右边的最大值

        int length = nums.length;

        int lmax = Integer.MIN_VALUE, rmax = Integer.MIN_VALUE;

        int temp = 1;

        // 从左到右找最大值

        for (int i = 0; i < length; ++i) {

            temp *= nums[i];

            // 保存最大值

            lmax = temp > lmax ? temp : lmax;

            // 遇到0就重新来，temp归1

            if (temp == 0) temp = 1;

        }

        temp = 1;

        // 从右到左找到最大值

        for (int i = length - 1; i >= 0; i--) {

            temp *= nums[i];

            rmax = temp > rmax ? temp : rmax;

            if (temp == 0) temp = 1;

        }

        return lmax >= rmax ? lmax : rmax;

    }

}