Skip to content
AI360Xpert
Back to 1-D Dynamic Programming
Medium

Maximum Product Subarray

Given an integer array `nums`, find a contiguous non-empty subarray within the array 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. A subarray is a contiguous subsequence of the array.

Examples

Input:nums = [2,3,-2,4]
Output:6
[2,3] has the largest product 6.
Input:nums = [-2,0,-1]
Output:0
The result cannot be 2, because [-2,-1] is not a subarray.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Dynamic Programming (Tracking Min and Max)

Approach

Unlike the maximum subarray sum (Kadane's algorithm), multiplying by a negative number can turn a very small (negative) product into a very large (positive) product. Therefore, at each step, we must keep track of both the maximum product ending at the current element and the minimum product ending at the current element. For the current number `n`, the new maximum is `max(n, n * current_max, n * current_min)` and the new minimum is `min(n, n * current_max, n * current_min)`. We update our global maximum accordingly.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(1)

Time complexity is O(n) because we iterate through the array once. Space complexity is O(1) as we only use a few variables for tracking the running minimum and maximum.

Solution.java
class Solution {    public int maxProduct(int[] nums) {        if (nums == null || nums.length == 0) return 0;                int maxProd = nums[0];        int minProd = nums[0];        int result = nums[0];                for (int i = 1; i < nums.length; i++) {            int num = nums[i];                        // If the current number is negative, minProd and maxProd will swap their roles            int tempMax = Math.max(num, Math.max(maxProd * num, minProd * num));            minProd = Math.min(num, Math.min(maxProd * num, minProd * num));                        maxProd = tempMax;            result = Math.max(result, maxProd);        }                return result;    }}