[LeetCode] 152. Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

乘积最大子数组。

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

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

思路

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

这个题跟 53 题很像，53 题问的是加和最大的子数组，这个题问的是乘积最大的子数组。思路依然是动态规划，这里 dp[i] 的含义是以 num[i] 结尾的子数组的最大值是多少。初始值是 nums[0]，状态转移方程分如下几种情况，因为数组中会存在负数所以需要记录两个变量，一个是 max 一个是 min，记录遍历到当前位置 i 的时候，局部的最大值和最小值。记录最小值的原因是有可能下一个数字又是负数的话，再乘以这个最小值，会比之前记录到的最大值还要大。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int maxProduct(int[] nums) {
        // corner case
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // normal case
        int max = nums[0];
        int min = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int temp = max;
            max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
            res = Math.max(res, max);
        }
        return res;
    }
}

相关题目

53. Maximum Subarray
152. Maximum Product Subarray
918. Maximum Sum Circular Subarray
978. Longest Turbulent Subarray