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.

Practice

1. What does the Maximum Product Subarray problem ask you to find in an integer array?

easy

A. The subarray with the smallest product of its elements

B. The contiguous subarray with the largest sum of its elements

C. The contiguous subarray with the largest product of its elements

D. The subarray with the largest difference between elements

Solution

1. Step 1: Understand the problem statement

   The problem asks for a contiguous part of the array where the product of all elements is the highest possible.

2. Step 2: Compare options with problem goal

   Only The contiguous subarray with the largest product of its elements matches the goal of finding the maximum product of a contiguous subarray.

3. Final Answer:

   The contiguous subarray with the largest product of its elements -> Option C

4. Quick Check:

   Maximum product subarray = largest product contiguous segment [OK]

Hint: Look for largest product, not sum or difference [OK]

Common Mistakes:

• Confusing product with sum
• Ignoring the contiguous subarray condition
• Thinking about smallest product instead

2. Which of the following Python code snippets correctly initializes variables to track the maximum product subarray?

easy

A. max_prod = None; min_prod = None; result = None

B. max_prod = 0; min_prod = 0; result = 0

C. max_prod = float('inf'); min_prod = float('-inf'); result = 0

D. max_prod = nums[0]; min_prod = nums[0]; result = nums[0]

Solution

1. Step 1: Understand initialization for max and min products

   We start with the first element as initial max, min, and result because the subarray must include at least one element.

2. Step 2: Check each option's correctness

   max_prod = nums[0]; min_prod = nums[0]; result = nums[0] correctly initializes all three variables to the first element of the array, which is standard practice.

3. Final Answer:

   max_prod = nums[0]; min_prod = nums[0]; result = nums[0] -> Option D

4. Quick Check:

   Initialize with first element to track products [OK]

Hint: Initialize with first element, not zero or None [OK]

Common Mistakes:

• Initializing with zero causes wrong results if array has negatives
• Using None causes errors in multiplication
• Using infinity values breaks logic

3. What is the output of the following code?

def maxProduct(nums):
    max_prod = min_prod = result = nums[0]
    for n in nums[1:]:
        candidates = (n, max_prod * n, min_prod * n)
        max_prod = max(candidates)
        min_prod = min(candidates)
        result = max(result, max_prod)
    return result

print(maxProduct([2,3,-2,4]))

medium

A. 24

B. 6

C. -2

D. 4

Solution

1. Step 1: Trace the loop with input [2,3,-2,4]

   Start: max_prod = min_prod = result = 2 Iteration 1 (n=3): candidates = (3, 2*3=6, 2*3=6) max_prod=6, min_prod=3, result=6 Iteration 2 (n=-2): candidates = (-2, 6*(-2)=-12, 3*(-2)=-6) max_prod=-2, min_prod=-12, result=6 Iteration 3 (n=4): candidates = (4, -2*4=-8, -12*4=-48) max_prod=4, min_prod=-48, result=6

2. Step 2: Determine final result

   The maximum product found during iterations is 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Maximum product subarray = 6 [OK]

Hint: Track max and min products each step [OK]

Common Mistakes:

• Ignoring min product when negative flips sign
• Only tracking max product causes wrong answer
• Not updating result each iteration

4. Find the error in this code snippet for maximum product subarray:

def maxProduct(nums):
    max_prod = min_prod = result = 0
    for n in nums:
        temp_max = max_prod
        max_prod = max(n, max_prod * n, min_prod * n)
        min_prod = min(n, temp_max * n, min_prod * n)
        result = max(result, max_prod)
    return result

medium

A. Initializing max_prod, min_prod, and result to 0 instead of nums[0]

B. Using temp_max instead of max_prod directly

C. Not iterating from second element

D. Returning result instead of max_prod

Solution

1. Step 1: Check variable initialization

   Initializing max_prod, min_prod, and result to 0 causes errors if all numbers are negative or first element is not zero.

2. Step 2: Compare with correct initialization

   Correct approach initializes these variables to nums[0] to handle negative and positive values properly.

3. Final Answer:

   Initializing max_prod, min_prod, and result to 0 instead of nums[0] -> Option A

4. Quick Check:

   Initialize with first element, not zero [OK]

Hint: Always initialize with first element, not zero [OK]

Common Mistakes:

• Starting max/min product at zero causes wrong results
• Not handling negative numbers properly
• Forgetting to update result each iteration

5. Given the array nums = [1, -2, -3, 0, 7, -8, -2], what is the maximum product of any contiguous subarray?

hard

A. 112

B. 48

C. 7

D. 0

Solution

1. Step 1: Identify subarrays with max product

   Check subarrays: - [1, -2, -3] product = 1 * -2 * -3 = 6 - [7] product = 7 - [7, -8, -2] product = 7 * -8 * -2 = 112 (since -8 * -2 = 16, 7 * 16 = 112) - Others are smaller or zero

2. Step 2: Confirm maximum product

   The largest product found is 112 from subarray [7, -8, -2].

3. Final Answer:

   112 -> Option A

4. Quick Check:

   Max product subarray = 112 [OK]

Hint: Check negative pairs that flip sign to positive [OK]

Common Mistakes:

• Ignoring negative number pairs that increase product
• Stopping at zero without checking after
• Only considering single elements