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.