Maximum Product Subarray

Problem

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.

 

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 prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let max = nums[0];
    const maxValueDp = [max];
    const minValueDp = [max];
    for (let i = 1; i < nums.length; i++) {
        const n = nums[i];
        if (n < 0) {
            maxValueDp.push(Math.max(minValueDp[i - 1] * n, n));
            minValueDp.push(Math.min(maxValueDp[i - 1] * n, n));
        } else {
            maxValueDp.push(Math.max(maxValueDp[i - 1] * n, n));
            minValueDp.push(Math.min(minValueDp[i - 1] * n, n));
        }
        max = Math.max(maxValueDp[i], max);
    }
    return max;
};

We will implement a DP solution. Let maxValueDp[i] and minValueDp[i] be the max and min product of the subarray ending and including nums[i].

• For the base case, if i = 0, then the max and min are both simply nums[i].
• For the recursive case:
  • If nums[i] is non-negative, the max must be either the previous max times the current element, or just the current element itself (ie. a larger number times a non-negative number is always larger compared to a smaller number times a non-negative number).
  • If nums[i] is negative, the max must be either the previous min times the current element, or just the current element itself (ie. a smaller number times a negative number is always larger compared to a larger number times a negative number).

Note that we also keep track of the global max product to return.

Note that we can lower the space complexity by only tracking the previous min and max instead of all of them.