‹ DS&A interview · Socratic
DSA · Dynamic Programming · #113

Maximum Product Subarray

Module 47 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given an integer array `nums`, find a **contiguous non-empty subarray** that has the **largest product**, and return that product. Implement the function `maxProduct(nums)` which returns the maximum product as a number. The answer fits in a 32-bit integer.

Examples
  • nums = [2,3,-2,4] → 6 — The subarray [2,3] has the largest product 6.
  • nums = [-2,0,-1] → 0 — The result is 0. Note [-2,-1] is not a contiguous subarray.
  • nums = [-2,3,-4] → 24 — The whole array: (-2)*3*(-4) = 24.
Constraints
  • · 1 <= nums.length <= 2 * 10^4
  • · -10 <= nums[i] <= 10
  • · The product of any contiguous subarray fits in a 32-bit integer.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.