Find Maximum Subarray Divide and Conquer in DSA Rust - Execution Trace

Concept Flow - Find Maximum Subarray Divide and Conquer

Divide array into two halves

↓

Find max subarray in left half

↓

Find max crossing subarray spanning middle

↓

Compare three max subarrays

↓

Return the one with maximum sum

The array is split into two halves recursively. We find the max subarray in left, right, and crossing the middle, then pick the best.

Execution Sample

DSA Rust

fn max_subarray(arr: &[i32]) -> (i32, usize, usize) {
    if arr.len() == 1 {
        return (arr[0], 0, 0);
    }
    let mid = arr.len() / 2;
    // recursive calls and combine results
}

This code finds the maximum subarray sum and its indices using divide and conquer.

Execution Table

Step	Operation	Subarray Range	Max Sum Found	Indices (start,end)	Visual State
1	Divide array	[0..7]	-	-	[3, -2, 5, -1, 6, -3, 2, 7]
2	Divide left half	[0..3]	-	-	[3, -2, 5, -1]
3	Divide left-left half	[0..1]	-	-	[3, -2]
4	Base case left-left-left	[0..0]	3	(0,0)	[3]
5	Base case left-left-right	[1..1]	-2	(1,1)	[-2]
6	Find max crossing left-left	[0..1]	3	(0,0)	[3, -2]
7	Max left-left	[0..1]	3	(0,0)	[3, -2]
8	Divide left-right half	[2..3]	-	-	[5, -1]
9	Base case left-right-left	[2..2]	5	(2,2)	[5]
10	Base case left-right-right	[3..3]	-1	(3,3)	[-1]
11	Find max crossing left-right	[2..3]	5	(2,2)	[5, -1]
12	Max left-right	[2..3]	5	(2,2)	[5, -1]
13	Find max crossing left	[0..3]	6	(0,2)	[3, -2, 5, -1]
14	Max left	[0..3]	6	(0,2)	[3, -2, 5, -1]
15	Divide right half	[4..7]	-	-	[6, -3, 2, 7]
16	Divide right-left half	[4..5]	-	-	[6, -3]
17	Base case right-left-left	[4..4]	6	(4,4)	[6]
18	Base case right-left-right	[5..5]	-3	(5,5)	[-3]
19	Find max crossing right-left	[4..5]	6	(4,4)	[6, -3]
20	Max right-left	[4..5]	6	(4,4)	[6, -3]
21	Divide right-right half	[6..7]	-	-	[2, 7]
22	Base case right-right-left	[6..6]	2	(6,6)	[2]
23	Base case right-right-right	[7..7]	7	(7,7)	[7]
24	Find max crossing right-right	[6..7]	9	(6,7)	[2, 7]
25	Max right-right	[6..7]	9	(6,7)	[2, 7]
26	Find max crossing right	[4..7]	12	(4,7)	[6, -3, 2, 7]
27	Max right	[4..7]	12	(4,7)	[6, -3, 2, 7]
28	Find max crossing whole array	[0..7]	17	(0,7)	[3, -2, 5, -1, 6, -3, 2, 7]
29	Compare left, right, crossing	[0..7]	17	(0,7)	[3, -2, 5, -1, 6, -3, 2, 7]
30	Return max subarray	[0..7]	17	(0,7)	[3, -2, 5, -1, 6, -3, 2, 7]

💡 All subproblems solved and combined, final max subarray found.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 14	After Step 20	After Step 27	Final
arr	[3, -2, 5, -1, 6, -3, 2, 7]	[3, -2, 5, -1, 6, -3, 2, 7]	[3, -2, 5, -1, 6, -3, 2, 7]	[3, -2, 5, -1, 6, -3, 2, 7]	[3, -2, 5, -1, 6, -3, 2, 7]	[3, -2, 5, -1, 6, -3, 2, 7]	[3, -2, 5, -1, 6, -3, 2, 7]
max_sum	-	3	3	6	6	12	17
start_index	-	0	0	0	4	4	0
end_index	-	0	0	2	4	7	7
mid	-	-	1	2	5	6	-

Key Moments - 3 Insights

Why do we check the max crossing subarray instead of just left and right halves?

Because the maximum subarray might cross the middle point, so checking only left or right halves misses that case. See execution_table rows 13, 26, and 28 where crossing sums are computed.

Why does the base case return the single element as max subarray?

Because when the subarray length is 1, that single element is the only possible subarray. See execution_table rows 4, 5, 9, 10, 17, 18, 22, 23.

How do we combine results from left, right, and crossing subarrays?

We compare their sums and pick the one with the largest sum. This is shown in execution_table row 29.

Visual Quiz - 3 Questions

Look at the execution_table at step 14, what is the max subarray sum and its indices for the left half?

A Sum 3, indices (0,0)

B Sum 5, indices (2,2)

C Sum 6, indices (0,2)

D Sum -1, indices (3,3)

💡 Hint

Check the 'Max left' row (step 14) in execution_table for max sum and indices.

At which step does the max crossing subarray for the right-right half get computed?

A Step 26

B Step 24

C Step 20

D Step 28

💡 Hint

Look for 'Find max crossing right-right' operation in execution_table.

If the array was all negative numbers, how would the base case results change?

A Base case would return the least negative single element as max subarray

B Base case would return zero as max sum

C Base case would return the entire array

D Base case would return no subarray

💡 Hint

Base case returns the single element itself, so the max sum is the largest single element even if negative.

Concept Snapshot

Divide array into halves recursively
Find max subarray in left, right, and crossing middle
Compare these three and return max
Base case: single element subarray
Crossing subarray found by expanding from middle
Time complexity: O(n log n)

Full Transcript

The divide and conquer method splits the array into two halves repeatedly. For each half, it finds the maximum subarray sum recursively. It also finds the maximum subarray that crosses the middle point by expanding from the middle to left and right. Then it compares the max subarrays from left half, right half, and crossing middle, returning the one with the largest sum. The base case is when the subarray has one element, which is the max subarray itself. This approach ensures all possible subarrays are considered efficiently. The execution table shows each step with the subarray ranges, sums found, and indices. The variable tracker follows key variables like max_sum and indices through the recursion. Key moments clarify why crossing subarrays are needed and how results combine. The visual quiz tests understanding of these steps. This method runs in O(n log n) time.

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