Skip to main content

73. Maximum Product Subarray

mediumAsked at Datadog

Find the contiguous subarray with the largest product. Datadog asks this for the dual-track DP trick (track both min and max) — same shape as anomaly detection that must handle bidirectional outliers.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — dual-track DP.

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.

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

Example 2

Input
nums = [-2,0,-1]
Output
0

Approaches

1. Brute force

All subarrays.

Time
O(n^2)
Space
O(1)
// Two nested loops computing each subarray product.

Tradeoff: Quadratic. Fails on 2*10^4 inputs.

2. Dual-track DP (optimal)

Track min AND max ending at i. Because a negative * current_min can flip to be the new max.

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

Tradeoff: Single pass. The min-tracking is essential — a current min times a future negative becomes a new max.

Datadog-specific tips

Datadog grades on whether you recognize that Kadane's classic doesn't work directly. The min/max swap on negatives is the key insight — articulate this BEFORE coding.

Common mistakes

  • Tracking only max — fails on inputs like [-2, 3, -4] where the answer requires the min to flip.
  • Forgetting the swap on negative — same bug.
  • Initializing best to 0 — fails on all-negative single-element inputs.

Follow-up questions

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

  • Maximum Subarray (LC 53) — additive version (Kadane's).
  • Subarray Sum Equals K (LC 560) — prefix-sum approach.
  • Datadog-style: bidirectional anomaly detection.

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 both min and max?

Multiplying by a negative flips min and max. If we only tracked max, a future negative would turn a 'bad' min into a new best.

Why swap on negative input?

The current max times negative = new min. The current min times negative = new max. Pre-swap so we don't lose either signal.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →