Skip to main content

85. Maximum Product Subarray

mediumAsked at Ola

Find the contiguous subarray with the largest product.

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

Problem

Given an integer array nums, find a contiguous non-empty subarray within the array (containing at least one number) which has the largest product, and return the product.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10

Examples

Example 1

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

Example 2

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

Approaches

1. Brute pairs

Try every subarray.

Time
O(n^2)
Space
O(1)
let best = -Infinity;
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:

2. Track max and min

Maintain running max and min product ending at current index; swap when current value is negative.

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];
    const candidates = [x, x * curMax, x * curMin];
    curMax = Math.max(...candidates);
    curMin = Math.min(...candidates);
    best = Math.max(best, curMax);
  }
  return best;
}

Tradeoff:

Ola-specific tips

Ola wants to see the curMax/curMin discipline; tie it to compounding a chain of surge multipliers that can flip sign through negative correction events.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →