Find Maximum Subarray Divide and Conquer in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle index of the array segment.

DSA Rust

let mid = (low + [1]) / 2;

Drag options to blanks, or click blank then click option'

Amid

Blow

Chigh

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using low twice instead of high.

Using mid variable before defining it.

The middle index is calculated by adding low and high indices and dividing by 2.

2fill in blank

medium

Complete the code to return the maximum of three values.

DSA Rust

return [1](left_sum, right_sum, cross_sum);

Drag options to blanks, or click blank then click option'

Amin

Bavg

Csum

Dmax

Attempts:

3 left

💡 Hint

Common Mistakes

Using min instead of max.

Using sum which adds all values.

We want the maximum sum among left, right, and crossing subarrays.

3fill in blank

hard

Fix the error in the loop to find the maximum crossing subarray sum on the left side.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Alow

Bmid

Chigh

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using high instead of low for left boundary.

Looping forward instead of backward.

The loop goes from mid down to low index to find max sum on left side.

4fill in blank

hard

Fill both blanks to find the maximum crossing subarray sum on the right side.

DSA Rust

sum = 0;
for j in (mid + 1)..=[1] {
    sum += arr[j];
    if sum > [2] {
        right_sum = sum;
    }
}

Drag options to blanks, or click blank then click option'

Ahigh

Bright_sum

Cleft_sum

Dsum

Attempts:

3 left

💡 Hint

Common Mistakes

Using left_sum instead of right_sum in comparison.

Using low instead of high for loop end.

The loop goes from mid+1 to high to find max sum on right side. We compare sum with right_sum.

5fill in blank

hard

Fill all four blanks to complete the recursive divide and conquer function call.

DSA Rust

let left_sum = find_max_subarray(arr, [1], mid);
let right_sum = find_max_subarray(arr, mid + 1, [2]);
let cross_sum = find_max_crossing_subarray(arr, [3], mid, [4]);

Drag options to blanks, or click blank then click option'

Alow

Bhigh

Cmid

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up low and high in parameters.

Using mid instead of high in last parameter.

Recursive calls use low to mid, mid+1 to high, and crossing uses low, mid, high.

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