Skip to main content

152. Maximum Product Subarray

medium

Find the contiguous subarray with the largest product. Trickier than Maximum Subarray — negatives flip signs, so you have to track both the running max AND the running min.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

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.

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sum version (Kadane's) won't work directly because of sign flips.

Hint 2

A negative * negative = positive, so the current minimum can become the new maximum once another negative is multiplied in.

Hint 3

Track BOTH currMax and currMin. At each step the candidates are nums[i] alone, currMax * nums[i], and currMin * nums[i].

Solution approach

Reveal approach

Modified Kadane's tracking max AND min. Initialize currMax = currMin = result = nums[0]. For i = 1..n-1: candidates = [nums[i], currMax * nums[i], currMin * nums[i]]; newMax = max(candidates); newMin = min(candidates); currMax = newMax; currMin = newMin; result = max(result, currMax). The min is tracked because multiplying a large negative min by a future negative can produce the largest positive product. O(n) time, O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • kadane

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • LinkedIn

Practice these live with InterviewChamp.AI

Drill Maximum Product Subarray and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →