Maximum Product Subarray in DSA Python

Mental Model

We want to find the largest product of a continuous part of the list. Because multiplying by a negative can flip the sign, we keep track of both the biggest and smallest products so far.

Analogy: Imagine walking on a path where stepping on a slippery stone (negative number) can suddenly change your direction. To know how far you can go positively, you must remember both your best and worst steps because a bad step might turn into a good one later.

Array: [2] -> [-3] -> [4] -> [-1] -> [0] -> [5]
max_prod ↑ 2
min_prod ↑ 2
result  ↑ 2

Dry Run Walkthrough

Input: list: [2, -3, 4, -1, 0, 5]

Goal: Find the maximum product of any continuous subarray

Step 1: Start with first element: max_prod = 2, min_prod = 2, result = 2

Array: 2 -> -3 -> 4 -> -1 -> 0 -> 5
max_prod=2, min_prod=2, result=2

Why: Initialize with first element to start tracking products

Step 2: Process -3: swap max_prod and min_prod because -3 is negative; max_prod = max(-3, 2 * -3) = -3; min_prod = min(-3, 2 * -3) = -6; result = max(2, -3) = 2

Array: 2 -> [-3] -> 4 -> -1 -> 0 -> 5
max_prod=-3, min_prod=-6, result=2

Why: Negative flips max and min, so swap to keep track correctly

Step 3: Process 4: max_prod = max(4, -3 * 4) = 4; min_prod = min(4, -6 * 4) = -24; result = max(2, 4) = 4

Array: 2 -> -3 -> [4] -> -1 -> 0 -> 5
max_prod=4, min_prod=-24, result=4

Why: Calculate new max and min products including current element

Step 4: Process -1: swap max_prod and min_prod; max_prod = max(-1, -24 * -1) = 24; min_prod = min(-1, 4 * -1) = -4; result = max(4, 24) = 24

Array: 2 -> -3 -> 4 -> [-1] -> 0 -> 5
max_prod=24, min_prod=-4, result=24

Why: Negative flips max and min again, update result with new max

Step 5: Process 0: max_prod = max(0, 24 * 0) = 0; min_prod = min(0, -4 * 0) = 0; result = max(24, 0) = 24

Array: 2 -> -3 -> 4 -> -1 -> [0] -> 5
max_prod=0, min_prod=0, result=24

Why: Zero resets products, start fresh from next elements

Step 6: Process 5: max_prod = max(5, 0 * 5) = 5; min_prod = min(5, 0 * 5) = 5; result = max(24, 5) = 24

Array: 2 -> -3 -> 4 -> -1 -> 0 -> [5]
max_prod=5, min_prod=5, result=24

Why: Last element updates max product but result stays 24

Result:

Final max product subarray = 24
State: max_prod=5, min_prod=5, result=24

Annotated Code

DSA Python

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        max_prod = min_prod = result = nums[0]
        for i in range(1, len(nums)):
            if nums[i] < 0:
                max_prod, min_prod = min_prod, max_prod  # swap because negative flips signs
            max_prod = max(nums[i], max_prod * nums[i])  # max product ending here
            min_prod = min(nums[i], min_prod * nums[i])  # min product ending here
            result = max(result, max_prod)  # update global max
        return result

# Driver code
nums = [2, -3, 4, -1, 0, 5]
sol = Solution()
print(sol.maxProduct(nums))

if nums[i] < 0: max_prod, min_prod = min_prod, max_prod

swap max and min when current number is negative to handle sign flip

max_prod = max(nums[i], max_prod * nums[i])

update max product ending at current index

min_prod = min(nums[i], min_prod * nums[i])

update min product ending at current index

result = max(result, max_prod)

keep track of the overall maximum product found so far

Output

24

Complexity Analysis

Time: O(n) because we scan the list once, updating products at each step

Space: O(1) because we only keep a few variables, no extra data structures

vs Alternative: Naive approach tries all subarrays with O(n^2) or O(n^3) time, this method is much faster

Edge Cases

Single element list

Returns that element as max product

DSA Python

max_prod = min_prod = result = nums[0]

List with zeros

Zeros reset product calculations, starting fresh after zero

DSA Python

max_prod = max(nums[i], max_prod * nums[i])

All negative numbers with even count

Max product is product of all elements

DSA Python

if nums[i] < 0:
    max_prod, min_prod = min_prod, max_prod

When to Use This Pattern

When you need the maximum product of a continuous subarray and negatives can flip signs, use the max/min product tracking pattern to handle sign changes efficiently.

Common Mistakes

Mistake: Not swapping max and min products when encountering a negative number
Fix: Add swap of max_prod and min_prod before updating them when current number is negative

Mistake: Only tracking max product, ignoring min product which can become max after negative
Fix: Track both max and min products at each step

Summary

Finds the largest product of any continuous subarray in a list.

Use when you want the maximum product and the list can have negative and zero values.

Keep track of both maximum and minimum products at each step because negatives can flip signs.