Maximum Product Subarray in DSA Python - Execution Trace

Concept Flow - Maximum Product Subarray

Start with first element

↓

Initialize max_prod, min_prod, result

↓

For each next element

↓

Calculate temp max and min products

↓

Update max_prod and min_prod

↓

Update result if max_prod is greater

↓

Repeat until end of array

↓

Return result

We move through the array, keeping track of the maximum and minimum products ending at each position, updating the overall maximum product found.

Execution Sample

DSA Python

nums = [2,3,-2,4]
max_prod = min_prod = result = nums[0]
for i in range(1, len(nums)):
    temp = max_prod
    max_prod = max(nums[i], max_prod * nums[i], min_prod * nums[i])
    min_prod = min(nums[i], temp * nums[i], min_prod * nums[i])
    result = max(result, max_prod)
print(result)

This code finds the maximum product of any contiguous subarray in the list nums.

Execution Table

Step	Operation	Current Number	max_prod	min_prod	result	Visual State
0	Initialize	2	2	2	2	[2]
1	Process next element	3	6	3	6	[2 -> 3] max_prod=6, min_prod=3
2	Process next element	-2	6	-12	6	[2 -> 3 -> -2] max_prod=6, min_prod=-12
3	Process next element	4	24	-48	24	[2 -> 3 -> -2 -> 4] max_prod=24, min_prod=-48
4	End	-	-	-	24	Finished processing all elements

💡 Reached end of array, final maximum product is 24

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
max_prod	2	6	6	24	24
min_prod	2	3	-12	-48	-48
result	2	6	6	24	24
current number	2	3	-2	4	-

Key Moments - 3 Insights

Why do we track both max_prod and min_prod at each step?

Because a negative number can turn a small minimum product into a large maximum product when multiplied, as seen in step 2 where min_prod becomes -12 and helps find max_prod later.

Why do we update result only with max_prod and not min_prod?

Result tracks the maximum product found so far, so only max_prod can increase it. min_prod tracks the smallest product which might become max_prod later but is not directly used to update result.

What happens when the current number is negative?

max_prod and min_prod swap roles because multiplying by a negative flips signs. This is why we use a temporary variable to hold max_prod before updating min_prod.

Visual Quiz - 3 Questions

Look at the execution table at Step 2, what is the value of min_prod?

A -12

B 3

C -2

D 6

💡 Hint

Check the 'min_prod' column in the row for Step 2 in the execution_table.

At which step does the result variable first update to 6?

A Step 2

B Step 0

C Step 1

D Step 3

💡 Hint

Look at the 'result' column in the execution_table and find when it changes from 2 to 6.

If the array started with a negative number instead of 2, how would max_prod change at Step 0?

A max_prod would be positive

B max_prod would be negative

C max_prod would be zero

D max_prod would be unchanged

💡 Hint

max_prod starts as the first element, so if that is negative, max_prod is negative at start.

Concept Snapshot

Maximum Product Subarray:
- Track max_prod and min_prod at each element
- max_prod = max(current, max_prod*current, min_prod*current)
- min_prod = min(current, max_prod*current_before_update, min_prod*current)
- Update result with max_prod
- Handles negative numbers by tracking min_prod
- Returns max product of any contiguous subarray

Full Transcript

The Maximum Product Subarray problem finds the largest product of a contiguous subarray within an array. We start by initializing max_prod, min_prod, and result to the first element. Then for each next element, we calculate temporary max and min products considering the current number, max_prod times current, and min_prod times current. We update max_prod and min_prod accordingly. The result is updated if max_prod is greater than the current result. This approach handles negative numbers by tracking both max and min products because multiplying by a negative flips signs. The final result after processing all elements is the maximum product subarray.

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