Maximum Product Subarray in DSA Rust

Mental Model

We want to find the biggest product of any continuous part of the list. Because multiplying negatives can flip signs, we keep track of both the biggest and smallest products so far.

Analogy: Imagine walking on a path where stepping on some stones doubles your speed (positive), some slow you down (negative), and some stop you (zero). To find the fastest stretch, you remember both your fastest and slowest speeds because a slow speed might turn into a fast one if you step on a negative stone next.

Array: [2, 3, -2, 4]
Start: max_prod=2, min_prod=2, result=2
Indices:  0  1   2  3

Dry Run Walkthrough

Input: array: [2, 3, -2, 4]

Goal: Find the maximum product of any continuous subarray

Step 1: Initialize max_prod=2, min_prod=2, result=2 at index 0

max_prod=2, min_prod=2, result=2

Why: Start with the first element as the initial max and min product

Step 2: At index 1 (value=3), update max_prod=max(3, 2*3=6, 2*3=6)=6, min_prod=min(3, 2*3=6, 2*3=6)=3, result=max(2,6)=6

max_prod=6, min_prod=3, result=6

Why: 3 alone or multiplied by previous max/min can be max or min product

Step 3: At index 2 (value=-2), update max_prod=max(-2, 6*(-2)=-12, 3*(-2)=-6)=-2, min_prod=min(-2, -12, -6)=-12, result=max(6,-2)=6

max_prod=-2, min_prod=-12, result=6

Why: Consider candidates: num, prev_max*num, prev_min*num. Negative can make prev_min*num large positive later

Step 4: At index 3 (value=4), update max_prod=max(4, -2*4=-8, -12*4=-48)=4, min_prod=min(4, -8, -48)=-48, result=max(6,4)=6

max_prod=4, min_prod=-48, result=6

Why: 4 alone or multiplied by previous max/min can be max or min product

Result:

Maximum product subarray is 6

Annotated Code

DSA Rust

fn max_product_subarray(nums: &[i32]) -> i32 {
    if nums.is_empty() {
        return 0;
    }
    let mut max_prod = nums[0];
    let mut min_prod = nums[0];
    let mut result = nums[0];
    for &num in &nums[1..] {
        let cand1 = max_prod * num;
        let cand2 = min_prod * num;
        max_prod = std::cmp::max(num, std::cmp::max(cand1, cand2));
        min_prod = std::cmp::min(num, std::cmp::min(cand1, cand2));
        result = std::cmp::max(result, max_prod);
    }
    result
}

fn main() {
    let nums = [2, 3, -2, 4];
    let max_product = max_product_subarray(&nums);
    println!("Maximum product subarray is {}", max_product);
}

let cand1 = max_prod * num; let cand2 = min_prod * num;

Precompute previous max/min products with current number to consider extending subarrays

max_prod = std::cmp::max(num, std::cmp::max(cand1, cand2));

Update max product: max(num alone, prev_max*num, prev_min*num)

min_prod = std::cmp::min(num, std::cmp::min(cand1, cand2));

Update min product similarly to track potential large positive after negatives

result = std::cmp::max(result, max_prod);

Track the overall maximum product found

Output

Maximum product subarray is 6

Complexity Analysis

Time: O(n) because we scan the array once updating max and min products

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Naive approach tries all subarrays with O(n^2) or O(n^3) time, this method is much faster

Edge Cases

empty array

returns 0 as no subarray exists

DSA Rust

if nums.is_empty() {
    return 0;
}

array with one element

returns that element as max product

DSA Rust

let mut max_prod = nums[0];

array with zeros

zeros reset product calculation, handled naturally by max/min updates

DSA Rust

max_prod = std::cmp::max(num, std::cmp::max(cand1, cand2));

When to Use This Pattern

When you need the maximum product of a continuous subarray and negatives can flip signs, use the max/min product tracking pattern to handle sign changes efficiently.

Common Mistakes

Mistake: Only tracking max product and ignoring min product
Fix: Track both max and min products to handle negative numbers correctly

Mistake: Forgetting to consider 'num' alone as a candidate for new max/min
Fix: Always take max/min over num, prev_max*num, prev_min*num

Summary

Finds the maximum product of any continuous subarray in a list.

Use when you want the largest product segment and the array can have negative numbers.

Keep track of both maximum and minimum products because negatives can flip signs.

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