Maximum Product Subarray Easy 0 attempts
LeetCode ↗

Maximum Product Subarray

Easy Dynamic ProgrammingMemoization LeetCode

Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product. A negative number multiplied by another negative can produce a large positive, so both maximum and minimum products at each position must be tracked.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6 (subarray [2,3])

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Sample Input
—
Sample Output
—
Constraints
  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
Test Cases
Case 1
Args: [[2,3,-2,4]] Expected: 6
Case 2
Args: [[-2,0,-1]] Expected: 0
Topics
Dynamic ProgrammingMemoization

Track Min and Max

Maintain current min and max products (a negative min can become max when multiplied by negative).

function maxProduct(nums) {
  let max = nums[0], curMax = nums[0], curMin = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const temp = curMax;
    curMax = Math.max(nums[i], nums[i] * curMax, nums[i] * curMin);
    curMin = Math.min(nums[i], nums[i] * temp, nums[i] * curMin);
    max = Math.max(max, curMax);
  }
  return max;
}

Time: O(n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript