Skip to main content

152. Maximum Product Subarray

mediumAsked at LinkedIn

Given an integer array, find the contiguous subarray with the largest product. LinkedIn asks this on the DP round because negatives turn Kadane on its head — you need to track BOTH min and max running products to handle sign flips.

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

Source citations

Public interview reports confirming this problem appears in LinkedIn loops.

  • Glassdoor (2026-Q1)— LinkedIn SWE onsite reports list Maximum Product Subarray as the canonical DP follow-up after Maximum Subarray.
  • Blind (2025-11)— LinkedIn writeups describe the 'track min AND max' insight as the explicit signal.

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.

Approaches

1. Brute-force every subarray

Try every (i, j) pair; compute the product; track the max.

Time
O(n^2)
Space
O(1)
function maxProductBrute(nums) {
  let best = nums[0];
  for (let i = 0; i < nums.length; i++) {
    let p = 1;
    for (let j = i; j < nums.length; j++) {
      p *= nums[j];
      best = Math.max(best, p);
    }
  }
  return best;
}

Tradeoff: Correct and easy but O(n^2) — borderline TLE at n = 2 * 10^4. Mention it to contrast with the DP.

2. Track running min and max (optimal)

Maintain curMax and curMin (the largest and smallest products of any subarray ending at i). When nums[i] is negative, swap them BEFORE multiplying — a negative * curMin becomes the new candidate max.

Time
O(n)
Space
O(1)
function maxProduct(nums) {
  let curMax = nums[0], curMin = nums[0], best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const x = nums[i];
    if (x < 0) { [curMax, curMin] = [curMin, curMax]; }
    curMax = Math.max(x, curMax * x);
    curMin = Math.min(x, curMin * x);
    best = Math.max(best, curMax);
  }
  return best;
}

Tradeoff: O(n) and O(1) space. The reason for tracking curMin: a future negative number multiplied by curMin (which might be a large negative) can yield a new max. Kadane's 'extend or restart' generalizes via two variables.

LinkedIn-specific tips

LinkedIn interviewers want you to spot WHY you need curMin: a negative number times a large negative gives a large positive. Articulate: 'For Kadane on sums I track one max; for products with negatives I track both max and min because a future negative flips them.' That sentence is the entire insight. Be ready for: 'What if zeros are present?' — zero resets both curMax and curMin via the `Math.max(x, ...)` clause.

Common mistakes

  • Tracking only curMax (Kadane-style) — fails on inputs like [-2,-3] where the answer is 6.
  • Computing curMax = curMax * x without considering Math.max(x, ...) — fails to restart after a zero.
  • Not swapping curMin and curMax BEFORE multiplying when x is negative — order of operations matters.

Follow-up questions

An interviewer at LinkedIn may pivot to one of these next:

  • Maximum Subarray (LC 53) — the additive version, classic Kadane.
  • Subarray Product Less Than K (LC 713) — sliding window variant.
  • Maximum Product of Three Numbers (LC 628) — different problem, same negative-product insight.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why track min when we want the max?

Because of negative numbers. A subarray's min product might become the max after multiplying by a future negative. Two negatives make a positive — so the most-negative running product is a candidate future max.

What's the recurrence?

curMax[i] = max(nums[i], nums[i] * curMax[i-1], nums[i] * curMin[i-1]). curMin[i] = symmetric with min. The 'or just start fresh at nums[i]' clause handles zeros and sign flips.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Maximum Product Subarray and other LinkedIn interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →