Skip to main content

12. Maximum Product Subarray

mediumAsked at Brex

Find the contiguous subarray with the largest product — tests dynamic programming with sign-flip tracking, relevant to multi-currency gain/loss computations at Brex.

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

Problem

Given an integer array nums, find a contiguous non-empty subarray that has the largest product and return the product. The array can contain positive integers, negative integers, and zeros.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • Product of any prefix or suffix fits 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

Try every subarray and compute product, track max.

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

Tradeoff:

2. DP with min/max tracking

Track both the maximum and minimum product ending at each position because a large negative times a future negative yields a large positive. Update both at every step.

Time
O(n)
Space
O(1)
function maxProduct(nums) {
  let maxProd = nums[0], minProd = nums[0], result = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const candidates = [nums[i], maxProd * nums[i], minProd * nums[i]];
    maxProd = Math.max(...candidates);
    minProd = Math.min(...candidates);
    result = Math.max(result, maxProd);
  }
  return result;
}

Tradeoff:

Brex-specific tips

Brex asks about fintech infrastructure, multi-currency handling, and spend management algorithms. Expect LeetCode-style DSA focused on hash maps, sorting, and dynamic programming.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →