乘积最大子数组

152. 乘积最大子数组

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

示例 1:

输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。示例 2:

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-product-subarray 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

使用动态规划的解题思路，递推出最终结果.

遍历数组时计算出最大值，不断更新，递推最终结果
res为最终结果， max为以当前元素结尾的子数组的最大乘积，min为以当前元素结尾的子数组的最小乘积
由于存在负数，所以要维护一个最小值，因为负数乘积可能变为一个最大值。

代码如下：

public static int maxProduct(int[] nums) {

        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        // 最终结果
        int res = nums[0];

        // 以i结尾的子数组的最大乘积
        int max = nums[0];
        // 以i结尾的子数组的组小乘积
        int min = nums[0];

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

            int tmp = max;
            max = Math.max(Math.max(max * nums[i],nums[i]),min * nums[i]);
            min = Math.min(Math.min(tmp * nums[i],nums[i]),min * nums[i]);

            res = Math.max(res,max);
        }

        return res;
    }

时间复杂度: O(N)

空间复杂度: O(1)

Table of Contents

152. 乘积最大子数组

题解

代码如下：