Maximum Product Subarray in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Product Subarray Calculation

What is the output of the following code that finds the maximum product of a contiguous subarray?

DSA Python

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

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

A 6

B 4

C 8

D -2

💡 Hint

Think about how negative numbers affect the product and why we track both max and min products.

The maximum product subarray is [2,3] with product 6. The code tracks max and min products to handle negative numbers correctly.

❓ Predict Output

intermediate

Result of Maximum Product Subarray with Negative Numbers

What is the output of this code for the input array containing negative numbers?

DSA Python

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

print(max_product_subarray([-2,0,-1]))

A -2

B -1

C 0

D 1

💡 Hint

Remember zero resets the product, so consider subarrays around zero.

The maximum product subarray is [0] with product 0. Negative numbers and zero reset the product tracking.

🔧 Debug

advanced

Identify the Error in Maximum Product Subarray Implementation

What error will this code produce when run, and why?

DSA Python

def max_product_subarray(nums):
    max_prod = min_prod = result = 0
    for num in nums:
        candidates = (num, max_prod * num, min_prod * num)
        max_prod = max(candidates)
        min_prod = min(candidates)
        result = max(result, max_prod)
    return result

print(max_product_subarray([-2]))

A The output is -2

B The output is 0

C The output is 24

D The output is 6

💡 Hint

Check the initial values of max_prod, min_prod, and result.

Initializing max_prod, min_prod, and result to 0 causes incorrect tracking because the first element might be positive and greater than 0, but the code never sets them to the first element's value.

🧠 Conceptual

advanced

Why Track Both Maximum and Minimum Products?

Why does the maximum product subarray algorithm track both the maximum and minimum products at each step?

A Because the minimum product can become maximum if multiplied by a negative number

B Because minimum product helps to find the smallest subarray length

C Because maximum product alone is enough to find the answer

D Because minimum product tracks the sum of negative numbers

💡 Hint

Think about how multiplying two negative numbers affects the product.

Tracking the minimum product is important because multiplying it by a negative number can turn it into a large positive product, which might be the maximum.

🚀 Application

expert

Maximum Product Subarray Length Query

Given the array [1, -2, -3, 0, 7, -8, -2], what is the length of the contiguous subarray with the maximum product?

A 4

B 5

C 2

D 3

💡 Hint

Find the subarray with the maximum product first, then count its length.

The maximum product subarray is [7, -8, -2] with product 112 and length 3. Zero resets the product, so subarrays containing zero are considered separately.

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