#152MediumDynamic Programming

Maximum Product Subarray

Track both max and min products — negatives can flip to become the max.

AmazonLinkedInMicrosoftLyft

Problem Statement

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.

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 since [-2,-1] is not a subarray.

Constraints

  • 1 ≤ nums.length ≤ 2 × 10⁴
  • -10 ≤ nums[i] ≤ 10
  • The product of any prefix or suffix of nums fits in a 32-bit integer.

Solutions

1
Brute Force
TimeO(n²)SpaceO(1)

Try all subarrays and compute their products. O(n²) or O(n³).

Visual Animation
def maxProduct(nums: list[int]) -> int:
    best = float(@@0@@)
    for i in range(len(nums)):
        prod = 1
        for j in range(i, len(nums)):
            prod *= nums[j]
            best = max(best, prod)
    return best

Related Concepts

Deepen your understanding with these related topics from our AI Glossary:

Dynamic Programming ConceptBrowse all 190+ concepts →
Deepen your understanding

Want to master the core concepts?

Our free AI Glossary covers 190+ topics — from Dynamic Programming to Dynamic Programming, Machine Learning, SQL, and more. Structured learning tracks for every level.

Browse AI Glossary All Problems
39+
AI Models
₹69
Per day used
4
Languages

Stuck? Ask AI to explain it step by step.

Ask Claude, GPT-4o, or Gemini to debug your code, generate test cases, or walk through the intuition. 39+ models. Pay only on days you use it — no subscription required.

Free to start · No credit card required to explore

Get Started Free
Back to all problems