Maximum Product Subarray Easy 0 attempts
LeetCode ↗

Maximum Product Subarray

Easy Dynamic ProgrammingMemoization LeetCode

You're given an integer array nums. Find a non-empty contiguous subarray whose elements multiply together to the largest possible value, and return that product. Because multiplying two negative numbers flips the sign back to positive, you'll need to keep track of both the running maximum and running minimum product at each position.

Input Format
Implement maxProduct(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
nums = [2,3,-2,4]
Output
6

Example 2

Input
nums = [-2,0,-1]
Output
0
Constraints
  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • The product of any subarray fits in a signed 32-bit integer.
Test Cases (2)
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).

javascript
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