Find Maximum Subarray Divide and Conquer in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Subarray Sum Using Divide and Conquer

What is the output of this Rust code that finds the maximum subarray sum using divide and conquer?

DSA Rust

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 max_subarray_sum(arr: &[i32], left: usize, right: usize) -> i32 {
    if left == right {
        return arr[left];
    }
    let mid = (left + right) / 2;
    let left_max = max_subarray_sum(arr, left, mid);
    let right_max = max_subarray_sum(arr, mid + 1, right);
    let cross_max = max_crossing_sum(arr, left, mid, right);
    *[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_sum(&arr, 0, arr.len() - 1);
    println!("{}", max_sum);
}

A 7

B 6

C 5

D 4

💡 Hint

Think about the subarray with the largest sum that crosses the middle point.

The maximum subarray is [4, -1, 2, 1] which sums to 6. The divide and conquer approach finds this by checking left, right, and crossing sums.

🧠 Conceptual

intermediate

Understanding the Divide and Conquer Approach for Maximum Subarray

Which statement best describes the divide and conquer approach to find the maximum subarray sum?

A It divides the array into two halves, finds the maximum subarray sum in each half, and also finds the maximum subarray sum crossing the middle, then returns the maximum of these three.

B It sorts the array and then finds the maximum sum of consecutive elements.

C It uses a sliding window to find the maximum sum subarray in linear time.

D It uses dynamic programming to store maximum sums ending at each index.

💡 Hint

Divide and conquer splits the problem into smaller parts and combines results.

The divide and conquer method splits the array, solves for left and right halves, and also considers subarrays crossing the midpoint.

🔧 Debug

advanced

Identify the Error in Maximum Subarray Divide and Conquer Code

What error will this Rust code produce when trying to find the maximum subarray sum?

DSA Rust

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 {
        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 max_subarray_sum(arr: &[i32], left: usize, right: usize) -> i32 {
    if left == right {
        return arr[left];
    }
    let mid = (left + right) / 2;
    let left_max = max_subarray_sum(arr, left, mid);
    let right_max = max_subarray_sum(arr, mid + 1, right);
    let cross_max = max_crossing_sum(arr, left, mid, right);
    *[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_sum(&arr, 0, arr.len() - 1);
    println!("{}", max_sum);
}

A panic: index out of bounds

B infinite recursion causing stack overflow

C returns incorrect maximum sum

D compilation error due to missing semicolon

💡 Hint

Check the parameters passed to the recursive function calls.

The call max_subarray_sum(&arr, 0, arr.len()) uses arr.len() as right index, which is out of bounds since valid indices are 0 to arr.len()-1.

❓ Predict Output

advanced

Output of Maximum Subarray Sum for All Negative Numbers

What is the output of this Rust code when the input array contains all negative numbers?

DSA Rust

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

fn main() {
    let arr = [-8, -3, -6, -2, -5, -4];
    let max_sum = max_subarray_sum(&arr, 0, arr.len() - 1);
    println!("{}", max_sum);
}

A -28

B -8

C -2

D 0

💡 Hint

The maximum subarray in all negative numbers is the least negative single element.

The maximum subarray sum is -2, which is the largest (least negative) element in the array.

🚀 Application

expert

Maximum Subarray Sum with Indices Using Divide and Conquer

Which option correctly modifies the divide and conquer maximum subarray code to also return the start and end indices of the maximum subarray?

A Return only the max_sum and find indices by scanning the array after the function finishes.

B Use a global variable to track indices and update it inside the recursive calls.

C Modify the array to mark elements in the maximum subarray and then find indices by searching marked elements.

D Return a tuple (max_sum, start_index, end_index) from each function and update indices when combining left, right, and crossing sums.

💡 Hint

Think about how to carry index information through recursion.

Returning a tuple with sum and indices allows tracking the exact subarray during recursion and combining results correctly.

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