Why Find Maximum Subarray Divide and Conquer in DSA Rust?

The Big Idea

What if you could find the best profit period in seconds instead of hours by breaking the problem smartly?

The Scenario

Imagine you have a long list of daily profits and losses for your small business. You want to find the best period where you made the most money overall. Doing this by checking every possible period manually would take forever!

The Problem

Manually checking every possible start and end day to find the best profit period means looking at many combinations. This is slow and easy to make mistakes, especially if the list is very long.

The Solution

The divide and conquer method breaks the big problem into smaller parts, solves each part, and then combines the answers. This way, it finds the best profit period much faster and without missing any possibilities.

Before vs After

✗ Before

fn max_subarray_brute_force(arr: &[i32]) -> i32 {
    let mut max_sum = i32::MIN;
    for i in 0..arr.len() {
        for j in i..arr.len() {
            let sum: i32 = arr[i..=j].iter().sum();
            if sum > max_sum {
                max_sum = sum;
            }
        }
    }
    max_sum
}

✓ After

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_divide_and_conquer(arr: &[i32], low: usize, high: usize) -> i32 {
    if low == high {
        return arr[low];
    }
    let mid = (low + high) / 2;
    let left_max = max_subarray_divide_and_conquer(arr, low, mid);
    let right_max = max_subarray_divide_and_conquer(arr, mid + 1, high);
    let cross_max = max_crossing_subarray(arr, low, mid, high);
    *[left_max, right_max, cross_max].iter().max().unwrap()
}

What It Enables

This method lets you quickly find the most profitable period in a list, even if the list is very long, saving time and effort.

Real Life Example

A stock trader wants to find the best time window to buy and sell stocks to maximize profit. Using divide and conquer helps find this window fast, even with years of daily prices.

Key Takeaways

Manual checking is slow and error-prone for large lists.

Divide and conquer breaks the problem into smaller parts and combines results efficiently.

This method finds the maximum subarray sum faster and more reliably.

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