Find Maximum Subarray Divide and Conquer in DSA Rust

Mental Model

Split the array into two halves, find the max subarray in the left, right, and crossing the middle, then pick the best.

Analogy: Like dividing a chocolate bar into two parts, finding the best piece on the left, right, and the middle where they meet, then choosing the tastiest piece overall.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Split:  [ -2, 1, -3, 4 ] | [ -1, 2, 1, -5, 4 ]
          ↑ middle
We find max left, max right, and max crossing middle.

Dry Run Walkthrough

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

Goal: Find the maximum sum of any continuous subarray using divide and conquer

Step 1: Split array into left [-2,1,-3,4] and right [-1,2,1,-5,4]

Left: [-2,1,-3,4] | Right: [-1,2,1,-5,4]

Why: Divide problem into smaller parts to solve recursively

Step 2: Find max subarray in left half by splitting again

Left split: [-2,1] and [-3,4]

Why: Keep dividing until base case of single element

Step 3: Base case: max subarray of [-2] is -2, [1] is 1

Max left half: max(-2,1) = 1

Why: Single elements are max subarrays themselves

Step 4: Find max crossing subarray for [-2,1]

Crossing sum: max suffix left + max prefix right = -2 + 1 = -1

Why: Check subarrays crossing middle point

Step 5: Combine results for left half: max(1, -3, 4, crossing sums) = 4

Left max subarray sum = 4

Why: Pick the best subarray sum from left half

Step 6: Find max subarray in right half [-1,2,1,-5,4] similarly

Right max subarray sum = 3 (from [2,1])

Why: Recursively find max subarray in right half

Step 7: Find max crossing subarray crossing middle between left and right halves

Crossing sum = max suffix left (4) + max prefix right (-1 + 2 + 1 = 2) = 6

Why: Check subarrays crossing the middle point

Step 8: Final max subarray sum = max(left max 4, right max 3, crossing max 6) = 6

Max subarray sum = 6

Why: Choose the best among left, right, and crossing sums

Result:

Max subarray sum = 6

Annotated Code

DSA Rust

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

fn max_subarray(arr: &[i32], low: usize, high: usize) -> i32 {
    if low == high {
        return arr[low];
    }
    let mid = (low + high) / 2;
    let left_max = max_subarray(arr, low, mid);
    let right_max = max_subarray(arr, mid + 1, high);
    let cross_max = max_crossing_subarray(arr, low, mid, high);
    *[left_max, right_max, cross_max].iter().max().unwrap()
}

fn main() {
    let arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
    let max_sum = max_subarray(&arr, 0, arr.len() - 1);
    println!("Max subarray sum = {}", max_sum);
}

for i in (low..=mid).rev() { sum += arr[i]; if sum > left_sum { left_sum = sum; } }

Find max suffix sum on left side crossing mid

for j in mid + 1..=high { sum += arr[j]; if sum > right_sum { right_sum = sum; } }

Find max prefix sum on right side crossing mid

if low == high { return arr[low]; }

Base case: single element is max subarray

let left_max = max_subarray(arr, low, mid);

Recursively find max subarray in left half

let right_max = max_subarray(arr, mid + 1, high);

Recursively find max subarray in right half

let cross_max = max_crossing_subarray(arr, low, mid, high);

Find max subarray crossing middle

*[left_max, right_max, cross_max].iter().max().unwrap()

Return the maximum among left, right, and crossing max sums

Output

Max subarray sum = 6

Complexity Analysis

Time: O(n log n) because the array is split into halves recursively and each merge step takes O(n) to find crossing max

Space: O(log n) due to recursion stack depth for splitting the array

vs Alternative: Better than naive O(n^2) approach that checks all subarrays by using divide and conquer to reduce repeated work

Edge Cases

Array with single element

Returns that element as max subarray sum

DSA Rust

if low == high { return arr[low]; }

Array with all negative numbers

Returns the largest (least negative) single element

DSA Rust

left_sum and right_sum initialized to i32::MIN to handle negatives

Array with all positive numbers

Returns sum of entire array

DSA Rust

Crossing sum calculation includes all elements if beneficial

When to Use This Pattern

When asked to find the maximum sum of a continuous subarray efficiently, recognize the divide and conquer pattern that splits the problem and combines results from left, right, and crossing middle.

Common Mistakes

Mistake: Not handling the crossing subarray correctly by missing the max suffix or prefix sums
Fix: Calculate max suffix sum on left and max prefix sum on right separately and add them

Mistake: Forgetting base case of single element leading to infinite recursion
Fix: Add base case check: if low == high, return arr[low]

Summary

Finds the maximum sum of any continuous subarray using divide and conquer.

Use when you want a more efficient solution than checking all subarrays directly.

Split array, find max subarrays in left, right, and crossing middle, then pick the best.

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