Find Maximum Subarray Divide and Conquer in DSA Rust - Build from Scratch

Find Maximum Subarray Divide and Conquer

📖 Scenario: You are analyzing daily temperature changes to find the longest warm spell. The temperature changes are recorded as a list of integers, where positive numbers mean warmer days and negative numbers mean colder days.You want to find the continuous period with the highest total temperature increase using the divide and conquer method.

🎯 Goal: Build a Rust program that uses the divide and conquer approach to find the maximum sum of a continuous subarray in a list of integers.

📋 What You'll Learn

Create a vector of integers named temp_changes with the exact values: [2, -4, 3, 5, -1, 2, -4, 3]

Create a helper function max_crossing_sum that finds the maximum sum crossing the middle of the array

Create a recursive function max_subarray_sum that uses divide and conquer to find the maximum subarray sum

Print the maximum subarray sum found

💡 Why This Matters

🌍 Real World

Finding maximum subarrays helps in analyzing trends like temperature changes, stock price gains, or sales increases over time.

💼 Career

Understanding divide and conquer algorithms and recursion is essential for software engineering roles involving algorithm design and optimization.

1

Create the temperature changes vector

Create a vector called temp_changes with these exact integers: 2, -4, 3, 5, -1, 2, -4, 3

DSA Rust

# Create the vector temp_changes with the given values
# Your code here

Hint

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

2

Add the max_crossing_sum helper function

Add a function called max_crossing_sum that takes arr: &Vec, left: usize, mid: usize, and right: usize and returns an i32. It should find the maximum sum of a subarray crossing the middle index.

DSA Rust

fn main() {
    let temp_changes = vec![2, -4, 3, 5, -1, 2, -4, 3];
}

// Add the max_crossing_sum function below
// Your code here

Hint

Use two loops: one going left from mid, one going right from mid+1, to find max sums.

3

Add the max_subarray_sum recursive function

Add a recursive function called max_subarray_sum that takes arr: &Vec, left: usize, and right: usize and returns an i32. It should use divide and conquer to find the maximum subarray sum.

DSA Rust

fn max_crossing_sum(arr: &Vec, left: usize, mid: usize, right: usize) -> i32 {
    // existing code
}

// Add the max_subarray_sum function below
// Your code here

fn main() {
    let temp_changes = vec![2, -4, 3, 5, -1, 2, -4, 3];
}

Hint

Use recursion to find max sums on left, right, and crossing middle, then return the max.

4

Print the maximum subarray sum

Use println! to print the maximum subarray sum by calling max_subarray_sum(&temp_changes, 0, temp_changes.len() - 1).

DSA Rust

fn max_crossing_sum(arr: &Vec, left: usize, mid: usize, right: usize) -> i32 {
    // existing code
}

fn max_subarray_sum(arr: &Vec, left: usize, right: usize) -> i32 {
    // existing code
}

fn main() {
    let temp_changes = vec![2, -4, 3, 5, -1, 2, -4, 3];
    // Print the maximum subarray sum below
    // Your code here
}

Hint

Call max_subarray_sum(&temp_changes, 0, temp_changes.len() - 1) inside println!.

Practice

1. What is the main idea behind the Divide and Conquer approach to find the maximum subarray in an array?

easy

A. Split the array into two halves, find max subarray in left, right, and crossing middle, then combine results

B. Sort the array and pick the largest element as the max subarray

C. Use a sliding window to check all subarrays in one pass

D. Calculate the sum of all elements and return it as max subarray

Solution

1. Step 1: Understand the divide step

   The array is split into two halves to simplify the problem into smaller parts.

2. Step 2: Combine results from subproblems

   Find max subarray in left half, right half, and subarray crossing the middle, then pick the maximum among these.

3. Final Answer:

   Split array, solve halves, combine crossing max -> Option A

4. Quick Check:

   Divide and conquer = split and combine max [OK]

Hint: Divide array, conquer halves, combine crossing max [OK]

Common Mistakes:

• Thinking sorting helps find max subarray
• Ignoring subarray crossing the middle
• Assuming max subarray is always a single element

2. Which of the following Rust function signatures correctly represents the divide and conquer function to find maximum subarray in a slice of integers?

easy

A. fn max_subarray(arr: Vec<i32>) -> usize

B. fn max_subarray(arr: &[i32], left: usize, right: usize) -> i32

C. fn max_subarray(arr: &mut [i32]) -> bool

D. fn max_subarray(arr: &[i32]) -> String

Solution

1. Step 1: Identify correct parameter types

   The function should take a slice reference and indices for left and right bounds.

2. Step 2: Identify correct return type

   The function returns the maximum sum as an integer (i32).

3. Final Answer:

   fn max_subarray(arr: &[i32], left: usize, right: usize) -> i32 -> Option B

4. Quick Check:

   Slice + indices + i32 return = fn max_subarray(arr: &[i32], left: usize, right: usize) -> i32 [OK]

Hint: Use slice and indices, return max sum i32 [OK]

Common Mistakes:

• Using Vec instead of slice reference
• Returning wrong type like bool or String
• Missing left and right index parameters

3. What is the output of the following Rust code snippet that uses divide and conquer to find the maximum subarray sum?

fn max_crossing_sum(arr: &[i32], left: usize, mid: usize, right: usize) -> i32 {
    let mut sum = 0;
    let mut left_sum = i32::MIN;
    for i in (left..=mid).rev() {
        sum += arr[i];
        if sum > left_sum {
            left_sum = sum;
        }
    }
    sum = 0;
    let mut right_sum = i32::MIN;
    for i in mid+1..=right {
        sum += arr[i];
        if sum > right_sum {
            right_sum = sum;
        }
    }
    left_sum + right_sum
}

fn main() {
    let arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
    let result = max_crossing_sum(&arr, 0, 4, 8);
    println!("{}", result);
}

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Calculate left sum from mid=4 to left=0

   Sum backward: i=4: sum=-1, left_sum=-1; i=3: sum=3, left_sum=3; i=2: sum=0; i=1: sum=1; i=0: sum=-1; max left_sum = 3

2. Step 2: Calculate right sum from mid+1=5 to right=8

   Sum forward: i=5: sum=2, right_sum=2; i=6: sum=3, right_sum=3; i=7: sum=-2; i=8: sum=2; max right_sum = 3

3. Step 3: Add left_sum and right_sum

   3 + 3 = 6

4. Final Answer:

   6 -> Option A

5. Quick Check:

   Max crossing sum = 6 [OK]

Hint: Sum left max + right max crossing mid [OK]

Common Mistakes:

• Not reversing left loop correctly
• Adding sums incorrectly
• Using wrong indices for loops

4. Identify the bug in this Rust function for finding the maximum subarray sum using divide and conquer:

fn max_subarray(arr: &[i32], left: usize, right: usize) -> i32 {
    if left == right {
        return arr[left];
    }
    let mid = (left + right) / 2;
    let left_sum = max_subarray(arr, left, mid);
    let right_sum = max_subarray(arr, mid + 1, right);
    let cross_sum = max_crossing_sum(arr, left, mid, right);
    left_sum.max(right_sum).max(cross_sum)
}

What is the likely cause of a runtime panic when calling this function with an empty array?

medium

A. Using max() function incorrectly

B. Integer overflow in calculating mid index

C. max_crossing_sum function is missing

D. Accessing arr[left] when left == right on empty array causes out-of-bounds panic

Solution

1. Step 1: Check base case for empty array

   If array is empty, left and right indices are invalid, so arr[left] access causes panic.

2. Step 2: Understand panic cause

   Accessing arr[left] when left == right but array length is zero triggers out-of-bounds error.

3. Final Answer:

   Accessing arr[left] on empty array causes panic -> Option D

4. Quick Check:

   Empty array access = panic [OK]

Hint: Check array length before accessing indices [OK]

Common Mistakes:

• Ignoring empty array edge case
• Assuming mid calculation causes overflow
• Thinking max_crossing_sum absence causes panic

5. Given the array [3, -2, 5, -1, 6, -3, 2, 7, -5, 2], what is the maximum subarray sum found using the divide and conquer approach?

hard

A. 15

B. 16

C. 17

D. 14

Solution

1. Step 1: Identify max subarray candidates

   Check subarrays: [3, -2, 5, -1, 6, -3, 2, 7] sums to 17, [5, -1, 6, -3, 2, 7] sums to 16, [3, -2, 5, -1, 6] sums to 11.

2. Step 2: Find max sum subarray

   The subarray [3, -2, 5, -1, 6, -3, 2, 7] has the maximum sum 17.

3. Final Answer:

   17 -> Option C

4. Quick Check:

   Max sum subarray = 17 [OK]

Hint: Check sums crossing mid for max total [OK]

Common Mistakes:

• Choosing sum of entire array
• Ignoring negative values inside subarray
• Not considering crossing subarrays