Find Maximum Subarray Divide and Conquer in DSA Python - 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 left max, right max, crossing max

↓

Return the max of three

↓

Combine results up the recursion

The array is split into halves recursively. We find max subarrays in left, right, and crossing middle parts, then pick the largest.

Execution Sample

DSA Python

def max_subarray(arr, low, high):
    if low == high:
        return (low, high, arr[low])
    mid = (low + high) // 2
    left = max_subarray(arr, low, mid)
    right = max_subarray(arr, mid+1, high)
    cross = max_crossing_subarray(arr, low, mid, high)
    return max(left, right, cross, key=lambda x: x[2])

This code finds the maximum subarray sum using divide and conquer by splitting the array and combining results.

Execution Table

Step	Operation	Subarray Range	Max Sum Found	Visual State
1	Divide array [0..4] into [0..2] and [3..4]	[0..4]	N/A	[1, -3, 2, 1, -1]
2	Divide left half [0..2] into [0..1] and [2..2]	[0..2]	N/A	[1, -3, 2]
3	Divide [0..1] into [0..0] and [1..1]	[0..1]	N/A	[1, -3]
4	Base case: single element [0..0]	[0..0]	1	[1]
5	Base case: single element [1..1]	[1..1]	-3	[-3]
6	Find crossing max subarray [0..1]	[0..1]	1	[1, -3]
7	Max left subarray in [0..1] is [0..0] sum=1	[0..1]	1	[1, -3]
8	Base case: single element [2..2]	[2..2]	2	[2]
9	Find crossing max subarray [0..2]	[0..2]	3	[1, -3, 2]
10	Max left subarray in [0..2] is [0..2] sum=3	[0..2]	3	[1, -3, 2]
11	Divide right half [3..4] into [3..3] and [4..4]	[3..4]	N/A	[1, -1]
12	Base case: single element [3..3]	[3..3]	1	[1]
13	Base case: single element [4..4]	[4..4]	-1	[-1]
14	Find crossing max subarray [3..4]	[3..4]	1	[1, -1]
15	Max right subarray in [3..4] is [3..3] sum=1	[3..4]	1	[1, -1]
16	Find crossing max subarray [0..4]	[0..4]	4	[1, -3, 2, 1, -1]
17	Compare left max=3, right max=1, crossing max=4	[0..4]	4	[1, -3, 2, 1, -1]
18	Return max subarray [0..3] with sum=4	[0..4]	4	[1, -3, 2, 1, -1]

💡 Recursion ends when subarray size is 1 (base case), then results combine up to full array.

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 8	After Step 12	After Step 13	After Step 16	Final
low	0	0	0	0	3	3	0	0
high	4	0	1	2	3	4	4	4
mid	2	0	0	1	3	3	2	2
max_left	N/A	(0,0,1)	(0,0,1)	(2,2,2)	(3,3,1)	(3,3,1)	(0,2,3)	(0,2,3)
max_right	N/A	(1,1,-3)	(1,1,-3)	(2,2,2)	(4,4,-1)	(4,4,-1)	(3,4,1)	(3,4,1)
max_cross	N/A	(0,1,1)	(0,1,1)	(0,2,3)	(3,4,1)	(3,4,1)	(0,3,4)	(0,3,4)
max_overall	N/A	(0,0,1)	(0,0,1)	(0,2,3)	(3,3,1)	(3,3,1)	(0,3,4)	(0,3,4)

Key Moments - 3 Insights

Why do we check the crossing subarray separately?

Because the maximum subarray might cross the middle point, so we must find the max sum that spans both halves (see steps 9, 16 in execution_table).

Why is the base case when low == high?

Because when the subarray has only one element, that element itself is the max subarray (see steps 4, 5, 8, 12, 13).

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

We compare their sums and pick the one with the largest sum as the max subarray for that range (see step 17).

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the max crossing subarray sum for [0..2]?

A 2

B 3

C 1

D -3

💡 Hint

Check the 'Max Sum Found' column at step 9 in execution_table.

At which step does the recursion reach the base case for the subarray [3..3]?

A Step 4

B Step 13

C Step 12

D Step 8

💡 Hint

Look for base case steps with single element subarrays in execution_table.

If the array was all negative numbers, how would the max subarray sum change in the variable_tracker?

A It would be the least negative single element

B It would be zero

C It would be the sum of the entire array

D It would be the sum of the first half

💡 Hint

Recall base case returns single element; max subarray in all negatives is the largest single element.

Concept Snapshot

Divide array into halves recursively
Find max subarray in left, right, and crossing middle
Compare these three max sums
Return the max as result
Base case: single element subarray
Crossing subarray found by expanding from middle

Full Transcript

The divide and conquer method splits the array into two halves repeatedly until single elements remain. For each split, it finds the maximum subarray in the left half, right half, and the subarray crossing the middle. It compares these three sums and returns the largest. This process combines results up the recursion to find the maximum subarray for the whole array. The base case is when the subarray has one element, which is the max subarray itself. The crossing subarray is found by expanding from the middle to include elements on both sides. This method efficiently finds the maximum sum subarray by breaking the problem into smaller parts and combining their solutions.

Practice

1. What is the main idea behind the Divide and Conquer approach to find the maximum subarray sum?

easy

A. Sort the array and pick the largest element

B. Divide the array into two halves, find max subarray in left, right, and crossing middle, then combine results

C. Use a sliding window to find the maximum sum

D. Calculate sum of all subarrays and pick the maximum

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 the subarray crossing the middle, then take the maximum of these three.

3. Final Answer:

   Divide the array into two halves, find max subarray in left, right, and crossing middle, then combine results -> Option B

4. Quick Check:

   Divide and conquer = split, solve, combine [OK]

Hint: Split array, solve halves, check crossing sum [OK]

Common Mistakes:

• Thinking sorting helps find max subarray
• Ignoring the crossing middle subarray
• Trying to sum all subarrays directly

2. Which of the following is the correct base case condition in the divide and conquer algorithm for maximum subarray?

easy

A. If the array length is 1, return the single element

B. If the array length is 1, return 0

C. If the array length is 2, return the sum of both elements

D. If the array length is 0, return 0

Solution

1. Step 1: Identify the smallest problem size

   The smallest subarray is a single element, so when length is 1, we return that element.

2. Step 2: Understand base case return value

   Return the single element because it is the maximum subarray sum for that subarray.

3. Final Answer:

   If the array length is 1, return the single element -> Option A

4. Quick Check:

   Base case = single element value [OK]

Hint: Base case returns single element value [OK]

Common Mistakes:

• Returning 0 instead of element for length 1
• Returning sum of two elements as base case
• Ignoring base case and causing infinite recursion

3. What is the output of the following code snippet using divide and conquer to find maximum subarray sum?

def max_crossing_sum(arr, left, mid, right):
    left_sum = float('-inf')
    total = 0
    for i in range(mid, left-1, -1):
        total += arr[i]
        if total > left_sum:
            left_sum = total
    right_sum = float('-inf')
    total = 0
    for j in range(mid+1, right+1):
        total += arr[j]
        if total > right_sum:
            right_sum = total
    return left_sum + right_sum

def max_subarray(arr, left, right):
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_max = max_subarray(arr, left, mid)
    right_max = max_subarray(arr, mid+1, right)
    cross_max = max_crossing_sum(arr, left, mid, right)
    return max(left_max, right_max, cross_max)

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(arr, 0, len(arr)-1))

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Understand the input array and function

   The array is [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The function finds max subarray sum using divide and conquer.

2. Step 2: Calculate maximum subarray sum manually

   The maximum subarray is [4, -1, 2, 1] with sum 4 + (-1) + 2 + 1 = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Look for max sum in continuous subarray [OK]

Common Mistakes:

• Choosing sum including -5 which lowers total
• Confusing max crossing sum with max overall
• Miscomputing indices in loops

4. Identify the bug in this divide and conquer max subarray code snippet:

def max_crossing_sum(arr, left, mid, right):
    left_sum = 0
    total = 0
    for i in range(mid, left-1, -1):
        total += arr[i]
        if total > left_sum:
            left_sum = total
    right_sum = 0
    total = 0
    for j in range(mid+1, right+1):
        total += arr[j]
        if total > right_sum:
            right_sum = total
    return left_sum + right_sum

medium

A. The total variable should not be reset inside the loops

B. The loops should run from left to mid and mid+1 to right

C. The function should return max(left_sum, right_sum), not their sum

D. left_sum and right_sum should start at negative infinity, not 0

Solution

1. Step 1: Analyze initial values of left_sum and right_sum

   They start at 0, which fails if all numbers are negative because max sum could be negative.

2. Step 2: Correct initialization

   Initialize left_sum and right_sum to negative infinity to correctly track max sums even if negative.

3. Final Answer:

   left_sum and right_sum should start at negative infinity, not 0 -> Option D

4. Quick Check:

   Init max sums to -inf to handle negatives [OK]

Hint: Use -inf for max sums to handle negative values [OK]

Common Mistakes:

• Starting max sums at 0 causes wrong results with negatives
• Changing loop directions incorrectly
• Returning sum instead of max of sums

5. Given an array arr = [3, -2, 5, -1, 6, -3, 2, 7, -5, 2], what is the maximum subarray sum found using divide and conquer? Also, which subarray produces this sum?

hard

A. Sum = 16, Subarray = [5, -1, 6, -3, 2, 7, -5, 2]

B. Sum = 14, Subarray = [5, -1, 6, -3, 2, 7]

C. Sum = 17, Subarray = [3, -2, 5, -1, 6, -3, 2, 7]

D. Sum = 18, Subarray = [3, -2, 5, -1, 6, -3, 2, 7, -5, 2]

Solution

1. Step 1: Calculate sums of candidate subarrays

   Check sums of given subarrays: - Sum = 14, Subarray = [5, -1, 6, -3, 2, 7]: 5 + (-1) + 6 + (-3) + 2 + 7 = 16 (not 14) - Sum = 17, Subarray = [3, -2, 5, -1, 6, -3, 2, 7]: 3 + (-2) + 5 + (-1) + 6 + (-3) + 2 + 7 = 17 - Sum = 16, Subarray = [5, -1, 6, -3, 2, 7, -5, 2]: 5 + (-1) + 6 + (-3) + 2 + 7 + (-5) + 2 = 13 (not 16) - Sum = 18, Subarray = [3, -2, 5, -1, 6, -3, 2, 7, -5, 2]: sum of entire array = 3 -2 +5 -1 +6 -3 +2 +7 -5 +2 = 14 (not 18)

2. Step 2: Identify maximum sum and subarray

   The maximum sum is 17 from subarray [3, -2, 5, -1, 6, -3, 2, 7].

3. Final Answer:

   Sum = 17, Subarray = [3, -2, 5, -1, 6, -3, 2, 7] -> Option C

4. Quick Check:

   Max sum = 17 from longest subarray [OK]

Hint: Sum subarrays carefully, check all candidates [OK]

Common Mistakes:

• Miscomputing sums with negative numbers
• Assuming max sum is entire array sum
• Ignoring subarray boundaries