Maximum Product Subarray in DSA Rust - Build from Scratch

Maximum Product Subarray

📖 Scenario: You are analyzing daily stock price changes represented as a list of integers. Each integer shows the daily change factor (positive for increase, negative for decrease, zero for no change). You want to find the maximum product of a contiguous subarray of these changes to understand the best period for investment growth.

🎯 Goal: Build a Rust program that finds the maximum product of any contiguous subarray within a list of integers.

📋 What You'll Learn

Create a vector called changes with the exact values: [2, 3, -2, 4]

Create two variables max_product and min_product initialized to the first element of changes

Use a for loop with variable i starting from 1 to iterate over changes

Inside the loop, update max_product and min_product considering the current element and previous products

Create a variable result to keep track of the maximum product found so far

Print the value of result at the end

💡 Why This Matters

🌍 Real World

Finding the maximum product subarray helps in financial analysis to identify the best period for investment growth based on daily changes.

💼 Career

Understanding this algorithm is useful for software engineers working on data analysis, finance, or any field that requires efficient subarray computations.

1

Create the data vector

Create a vector called changes with the exact values [2, 3, -2, 4].

DSA Rust

# Create the vector changes with values [2, 3, -2, 4]
// Your code here

Hint

Use let changes = vec![2, 3, -2, 4]; to create the vector.

2

Initialize product tracking variables

Create two variables max_product and min_product and set both to the first element of changes. Also create a variable result and set it to the first element of changes.

DSA Rust

fn main() {
    let changes = vec![2, 3, -2, 4];
    // Initialize max_product, min_product, and result to changes[0]
    // Your code here
}

Hint

Use let mut to create variables that will change. Initialize all three to changes[0].

3

Implement the main loop to find max product

Use a for loop with variable i starting from 1 to iterate over changes. Inside the loop, create a variable current for changes[i]. Then create temporary variables temp_max and temp_min to store the current max_product and min_product. Update max_product to the maximum of current, temp_max * current, and temp_min * current. Update min_product to the minimum of current, temp_max * current, and temp_min * current. Finally, update result to the maximum of result and max_product.

DSA Rust

fn main() {
    let changes = vec![2, 3, -2, 4];
    let mut max_product = changes[0];
    let mut min_product = changes[0];
    let mut result = changes[0];

    // Loop from i = 1 to changes.len() - 1
    // Your code here
}

Hint

Use for i in 1..changes.len() to loop. Use temporary variables to avoid overwriting before calculations. Use iter().max().unwrap() and iter().min().unwrap() to find max and min.

4

Print the maximum product result

Print the value of result using println!.

DSA Rust

fn main() {
    let changes = vec![2, 3, -2, 4];
    let mut max_product = changes[0];
    let mut min_product = changes[0];
    let mut result = changes[0];

    for i in 1..changes.len() {
        let current = changes[i];
        let temp_max = max_product;
        let temp_min = min_product;

        max_product = *[current, temp_max * current, temp_min * current].iter().max().unwrap();
        min_product = *[current, temp_max * current, temp_min * current].iter().min().unwrap();

        if max_product > result {
            result = max_product;
        }
    }

    // Print the result
    // Your code here
}

Hint

Use println!("{}", result); to print the maximum product.

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