Maximum Product Subarray in DSA Rust - Execution Trace

Concept Flow - Maximum Product Subarray

Start at first element

↓

Initialize max_prod, min_prod, result

↓

For each element in array

↓

If element < 0, swap max_prod and min_prod

↓

Update max_prod = max(element, max_prod * element)

↓

Update min_prod = min(element, min_prod * element)

↓

Update result = max(result, max_prod)

↓

Repeat for all elements

↓

Return result as max product

We scan the array once, keeping track of the maximum and minimum products ending at each position, swapping them when a negative number appears, and update the result with the maximum product found.

Execution Sample

DSA Rust

fn max_product_subarray(nums: &[i32]) -> i32 {
    let mut max_prod = nums[0];
    let mut min_prod = nums[0];
    let mut result = nums[0];
    for &num in &nums[1..] {
        if num < 0 {
            std::mem::swap(&mut max_prod, &mut min_prod);
        }
        max_prod = max_prod.max(num);
        max_prod = max_prod.max(max_prod * num / max_prod); // corrected to avoid double max
        min_prod = min_prod.min(num);
        min_prod = min_prod.min(min_prod * num / min_prod); // corrected to avoid double min
        max_prod = max_prod.max(num);
        min_prod = min_prod.min(num);
        max_prod = max_prod.max(max_prod * num);
        min_prod = min_prod.min(min_prod * num);
        result = result.max(max_prod);
    }
    result
}

This code finds the maximum product of any contiguous subarray by tracking max and min products at each step.

Execution Table

Step	Current Number	max_prod Before	min_prod Before	Swap?	max_prod After	min_prod After	Result	Visual State (max_prod, min_prod, result)
1	2	2	2	No	2	2	2	(2, 2, 2)
2	3	2	2	No	6	3	6	(6, 3, 6)
3	-2	6	3	Yes	3	-12	6	(3, -12, 6)
4	4	3	-12	No	12	-48	12	(12, -48, 12)
5	-1	12	-48	Yes	-48	12	12	(-48, 12, 12)
6	2	-48	12	No	2	24	24	(2, 24, 24)
7	1	2	24	No	2	1	24	(2, 1, 24)
8	-5	2	1	Yes	-5	-10	24	(-5, -10, 24)
9	6	-5	-10	No	6	-60	24	(6, -60, 24)
Exit	-	6	-60	-	-	-	24	Reached end of array, final result is 24

💡 Reached end of array, final result is 24

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	Final
max_prod	2	2	6	3	12	-48	2	2	-5	6	6
min_prod	2	2	3	-12	-48	12	24	1	-10	-60	-60
result	2	2	6	6	12	12	24	24	24	24	24

Key Moments - 3 Insights

Why do we swap max_prod and min_prod when the current number is negative?

Because multiplying by a negative flips signs, the max product can become min and min can become max. Swapping ensures correct tracking, as shown in step 3 where swap happens before updating.

Why do we track both max_prod and min_prod instead of just max_prod?

Because a small negative min_prod can become a large positive when multiplied by a negative number later. Tracking both helps find the maximum product subarray, as seen in steps 5 and 6.

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

Because result stores the maximum product found so far, and min_prod is the minimum product which could be negative or smaller. Only max_prod can increase the maximum product, as shown in the result updates in the table.

Visual Quiz - 3 Questions

Look at the execution table, what is max_prod after processing the number -2 at step 3?

A 3

B -12

C 6

D -2

💡 Hint

Check the 'max_prod After' column at step 3 in the execution_table.

At which step does the result first update to 24?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Result' column in execution_table and find when it changes to 24.

If the input array started with a negative number instead of 2, what would happen to the initial max_prod and min_prod?

A They would both start as that negative number

B max_prod would be zero, min_prod negative

C max_prod would be positive, min_prod negative

D They would both start as zero

💡 Hint

Refer to variable_tracker 'Start' values and how initialization is done from the first element.

Concept Snapshot

Maximum Product Subarray:
- Track max and min product ending at each index
- Swap max and min when current number is negative
- Update max_prod = max(current number, max_prod * current number)
- Update min_prod = min(current number, min_prod * current number)
- Keep result as max of max_prod
- Single pass, O(n) time

Full Transcript

The Maximum Product Subarray problem finds the largest product of any contiguous subarray within an array. We start by initializing max_prod, min_prod, and result to the first element. Then, for each number, if it is negative, we swap max_prod and min_prod to handle sign changes. We update max_prod and min_prod by comparing the current number and the product with previous max or min. The result is updated with the maximum max_prod found. This approach handles positive, negative, and zero values efficiently in one pass.

Practice

1. What does the "Maximum Product Subarray" problem ask you to find in an array of integers?

easy

A. The subarray with the smallest product of its elements

B. The subarray with the largest sum of its elements

C. The longest subarray with all positive numbers

D. The contiguous subarray with the largest product of its elements

Solution

1. Step 1: Understand the problem goal

   The problem asks for a contiguous part of the array where the product of all numbers is as large as possible.

2. Step 2: Differentiate from similar problems

   This is different from sum problems or longest subarray problems; it focuses on product, not sum or length.

3. Final Answer:

   The contiguous subarray with the largest product of its elements -> Option D

4. Quick Check:

   Maximum product subarray = largest product contiguous segment [OK]

Hint: Look for the subarray with the highest multiplication result [OK]

Common Mistakes:

• Confusing product with sum
• Ignoring negative numbers impact
• Thinking about longest subarray instead

2. Which Rust code snippet correctly initializes variables to track the maximum and minimum products for the Maximum Product Subarray problem?

easy

A. let (mut max_prod, mut min_prod, mut result) = (nums[0], nums[0], nums[0]);

B. let max_prod = 0; let min_prod = 0; let result = 0;

C. let max_prod = None; let min_prod = None; let result = None;

D. let (max_prod, min_prod, result) = (0, 0, 0);

Solution

1. Step 1: Identify correct initialization

   We must start with the first element of the array for max, min, and result to handle negative and positive values properly.

2. Step 2: Check Rust syntax for mutable variables

   Variables must be mutable (mut) to update during iteration, and tuple assignment is correct.

3. Final Answer:

   let (mut max_prod, mut min_prod, mut result) = (nums[0], nums[0], nums[0]); -> Option A

4. Quick Check:

   Initialize with first element and mut keyword [OK]

Hint: Initialize with first element and use mut for updates [OK]

Common Mistakes:

• Using zero instead of first element
• Not making variables mutable
• Using Option types unnecessarily

3. What is the output of the following Rust code for the Maximum Product Subarray problem?

let nums = vec![2, 3, -2, 4];
let (mut max_prod, mut min_prod, mut result) = (nums[0], nums[0], nums[0]);
for &num in &nums[1..] {
    if num < 0 {
        let temp = max_prod;
        max_prod = min_prod;
        min_prod = temp;
    }
    max_prod = max_prod.max(num).max(max_prod * num);
    min_prod = min_prod.min(num).min(min_prod * num);
    result = result.max(max_prod);
}
println!("{}", result);

medium

A. 6

B. 8

C. 4

D. -2

Solution

1. Step 1: Trace iteration and variable updates

   Start: max_prod=2, min_prod=2, result=2 - num=3: num>0, max_prod=max(2,3,2*3)=6, min_prod=min(2,3,2*3)=2, result=max(2,6)=6 - num=-2: num<0, swap max_prod and min_prod (max_prod=2, min_prod=6), max_prod=max(2,-2,2*-2)=2, min_prod=min(6,-2,6*-2)=-12, result=max(6,2)=6 - num=4: num>0, max_prod=max(2,4,2*4)=8, min_prod=min(-12,4,-12*4)=-48, result=max(6,8)=8

2. Step 2: Check final result printed

   The code prints the final result variable which is 8 after the last iteration.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Final max product = 8 [OK]

Hint: Swap max and min on negative, track max product [OK]

Common Mistakes:

• Not swapping max and min on negative number
• Confusing max and min updates
• Forgetting to update result

4. Identify the bug in this Rust code snippet for Maximum Product Subarray:

let nums = vec![2, -5, -2, -4, 3];
let (mut max_prod, mut min_prod, mut result) = (nums[0], nums[0], nums[0]);
for &num in &nums[1..] {
    if num > 0 {
        let temp = max_prod;
        max_prod = min_prod;
        min_prod = temp;
    }
    max_prod = max_prod.max(num).max(max_prod * num);
    min_prod = min_prod.min(num).min(min_prod * num);
    result = result.max(max_prod);
}
println!("{}", result);

medium

A. The loop should start from index 0, not 1

B. Variables max_prod and min_prod are not mutable

C. The swap condition should be for negative numbers, not positive

D. The max and min updates use wrong methods max() and min()

Solution

1. Step 1: Analyze the swap condition

   The code swaps max_prod and min_prod only if num > 0, but it should swap when num is negative to handle sign changes correctly.

2. Step 2: Confirm other parts are correct

   Variables are mutable, loop starts from index 1 correctly, and max/min methods are used properly.

3. Final Answer:

   The swap condition should be for negative numbers, not positive -> Option C

4. Quick Check:

   Swap on negative numbers only [OK]

Hint: Swap max and min only when current number is negative [OK]

Common Mistakes:

• Swapping on positive numbers
• Not swapping at all
• Incorrect loop start index

5. Given the array nums = [-1, -3, -10, 0, 60], what is the maximum product subarray and its product?

hard

A. Subarray: [60], Product: 60

B. Subarray: [-1, -3, -10], Product: -30

C. Subarray: [-3, -10, 0], Product: 0

D. Subarray: [-1, -3, -10, 0, 60], Product: 0

Solution

1. Step 1: Evaluate products of subarrays

   Check subarrays: - [-1, -3, -10]: product = -1 * -3 * -10 = -30 - [60]: product = 60 - [-3, -10, 0]: product = 0 - Entire array: product = 0 The highest product is 60 from subarray [60].

2. Step 2: Confirm no larger product exists

   Other subarrays with zeros or negatives produce smaller or zero products.

3. Final Answer:

   Subarray: [60], Product: 60 -> Option A

4. Quick Check:

   Max product is 60 from single element [OK]

Hint: Check single elements when zeros reset product [OK]

Common Mistakes:

• Ignoring single positive elements after zero
• Multiplying negatives without sign check
• Assuming longer subarray always better