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.