Maximum Product Subarray

Problem

Given an integer array nums, find a subarray that has the largest product, and return the product.

Examples

The brute-force approach

Try every subarray by iterating over all start and end indices. Track the maximum product.

best = nums[0]

for i in range(len(nums)):
    product = 1
    for j in range(i, len(nums)):    # extend right
        product *= nums[j]
        best = max(best, product)

return best

Checking every subarray is O(n²). The problem has optimal substructure: the best product ending at position i depends on what the best (and worst) product was ending at i-1. You can track both in a single pass.

Spotting the pattern

This is a Kadane's Algorithm problem. The key question to ask yourself:

Can I track both the running max and running min at each position, since a negative times a negative becomes a positive?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.