Maximum Product Subarray in DSA Python - Build from Scratch

Maximum Product Subarray

📖 Scenario: Imagine you are analyzing daily sales growth rates of a product over a week. These growth rates can be positive (growth), negative (decline), or zero (no change). You want to find the period where the product's sales growth multiplied together is the highest.

🎯 Goal: Build a program that finds the maximum product of a contiguous subarray within a list of integers representing daily growth rates.

📋 What You'll Learn

Create a list called growth_rates with the exact values: [2, 3, -2, 4]

Create a variable called max_product initialized to the first element of growth_rates

Use a for loop with index i starting from 1 to iterate over growth_rates

Inside the loop, update variables to track the maximum and minimum products ending at the current index

Print the final value of max_product

💡 Why This Matters

🌍 Real World

This algorithm helps businesses analyze periods of growth or decline by finding the best continuous stretch of positive impact in sales or stock prices.

💼 Career

Understanding this problem is useful for roles in data analysis, financial modeling, and software engineering where time series data and optimization are common.

1

Create the growth rates list

Create a list called growth_rates with these exact values: [2, 3, -2, 4]

DSA Python

# Create the list growth_rates with values [2, 3, -2, 4]
# Your code here

Hint

Use square brackets to create a list and separate values with commas.

2

Initialize max_product, min_product, and result

Create three variables called max_product, min_product, and result and set all of them to the first element of growth_rates

DSA Python

growth_rates = [2, 3, -2, 4]
# Initialize max_product, min_product, and result to growth_rates[0]
# Your code here

Hint

Set all three variables equal to the first element of the list using growth_rates[0].

3

Loop through growth_rates to find max product subarray

Use a for loop with variable i starting from 1 to iterate over growth_rates. Inside the loop, create a temporary variable temp_max to store the current max_product. Update max_product to the maximum of growth_rates[i], max_product * growth_rates[i], and min_product * growth_rates[i]. Update min_product to the minimum of growth_rates[i], temp_max * growth_rates[i], and min_product * growth_rates[i]. Update result to the maximum of result and max_product.

DSA Python

growth_rates = [2, 3, -2, 4]
max_product = growth_rates[0]
min_product = growth_rates[0]
result = growth_rates[0]
# Use a for loop starting from index 1 to update max_product, min_product, and result
# Your code here

Hint

Remember to save the old max_product in a temporary variable before updating it.

4

Print the maximum product subarray result

Print the value of result to display the maximum product of a contiguous subarray.

DSA Python

growth_rates = [2, 3, -2, 4]
max_product = growth_rates[0]
min_product = growth_rates[0]
result = growth_rates[0]
for i in range(1, len(growth_rates)):
    temp_max = max_product
    max_product = max(growth_rates[i], max_product * growth_rates[i], min_product * growth_rates[i])
    min_product = min(growth_rates[i], temp_max * growth_rates[i], min_product * growth_rates[i])
    result = max(result, max_product)
# Print the result
# Your code here

Hint

Use print(result) to show the final answer.

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