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

Concept Flow - Find Maximum Subarray Divide and Conquer

Start with full array

↓

Divide array into two halves

↓

Find max subarray in left half

↓

Find max crossing subarray

↓

Compare left, right, crossing max

↓

Return max subarray

↓

Done

Divide the array into halves, find max subarray in left, right, and crossing middle, then return the max of these three.

Execution Sample

DSA C

int maxCrossingSum(int arr[], int left, int mid, int right) {
  int sum = 0, left_sum = INT_MIN;
  for (int i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > left_sum) left_sum = sum;
  }
  sum = 0; int right_sum = INT_MIN;
  for (int i = mid + 1; i <= right; i++) {
    sum += arr[i];
    if (sum > right_sum) right_sum = sum;
  }
  return left_sum + right_sum;
}

This function finds the maximum subarray sum that crosses the middle point.

Execution Table

Step	Operation	Subarray Range	Max Left Sum	Max Right Sum	Cross Sum	Max Subarray Sum	Visual State
1	Divide full array	[0..7]	-	-	-	-	[2, -1, 3, 4, -2, 1, 5, -3]
2	Divide left half	[0..3]	-	-	-	-	[2, -1, 3, 4]
3	Divide left-left half	[0..1]	-	-	-	-	[2, -1]
4	Base case single element	[0..0]	2	-	-	2	[2]
5	Base case single element	[1..1]	-1	-	-	-1	[-1]
6	Max crossing sum [0..1]	[0..1]	2	-1	1	2	[2, -1]
7	Max left half max	[0..1]	2	-1	1	2	[2, -1]
8	Divide left-right half	[2..3]	-	-	-	-	[3, 4]
9	Base case single element	[2..2]	3	-	-	3	[3]
10	Base case single element	[3..3]	4	-	-	4	[4]
11	Max crossing sum [2..3]	[2..3]	3	4	7	7	[3, 4]
12	Max left half max	[0..3]	2	7	8	8	[2, -1, 3, 4]
13	Divide right half	[4..7]	-	-	-	-	[-2, 1, 5, -3]
14	Divide right-left half	[4..5]	-	-	-	-	[-2, 1]
15	Base case single element	[4..4]	-2	-	-	-2	[-2]
16	Base case single element	[5..5]	1	-	-	1	[1]
17	Max crossing sum [4..5]	[4..5]	-2	1	-1	1	[-2, 1]
18	Divide right-right half	[6..7]	-	-	-	-	[5, -3]
19	Base case single element	[6..6]	5	-	-	5	[5]
20	Base case single element	[7..7]	-3	-	-	-3	[-3]
21	Max crossing sum [6..7]	[6..7]	5	-3	2	5	[5, -3]
22	Max right half max	[4..7]	1	5	6	6	[-2, 1, 5, -3]
23	Max crossing sum full [0..7]	[0..7]	8	6	12	12	[2, -1, 3, 4, -2, 1, 5, -3]
24	Final max subarray sum	[0..7]	8	6	12	12	[2, -1, 3, 4, -2, 1, 5, -3]

💡 All subproblems solved, final max subarray sum is 12 for subarray [2, -1, 3, 4, -2, 1, 5]

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 12	After Step 17	After Step 21	After Step 22	After Step 23	Final
maxLeftSum	-	2	7	8	1	5	6	8	8
maxRightSum	-	-1	4	7	1	-3	5	6	6
crossSum	-	1	7	8	-1	2	6	12	12
maxSubarraySum	-	2	7	8	1	5	6	12	12

Key Moments - 3 Insights

Why do we calculate max crossing sum separately?

Because the maximum subarray might cross the middle point, so we must check the sum crossing left and right halves (see steps 6, 11, 17, 21, 23 in execution_table).

Why do we return the maximum of left, right, and crossing sums?

Because the max subarray can be fully in the left half, fully in the right half, or crossing the middle. We compare all three to find the overall max (see step 23).

What happens at base cases with single elements?

At base cases (steps 4,5,9,10,15,16,19,20), the max subarray is the element itself, so we return that element's value.

Visual Quiz - 3 Questions

Look at the execution_table at step 23, what is the max crossing sum for the full array?

A 6

B 12

C 8

D 7

💡 Hint

Check the 'Cross Sum' column at step 23 in execution_table.

At which step does the max subarray sum first become 7?

A Step 6

B Step 17

C Step 11

D Step 21

💡 Hint

Look at the 'Max Subarray Sum' column in execution_table and find when it first reaches 7.

If the array had all negative numbers, how would the base case steps change?

A Base cases would return the least negative element as max subarray.

B Base cases would return zero.

C Base cases would return the sum of all elements.

D Base cases would return positive infinity.

💡 Hint

Recall base cases return the single element value, so max subarray is the largest single element (see steps 4,5,9,10,15,16,19,20).

Concept Snapshot

Divide and Conquer approach to find max subarray:
- Divide array into halves
- Recursively find max subarray in left and right halves
- Find max crossing subarray crossing middle
- Return max of left, right, crossing sums
- Base case: single element subarray
- Time complexity: O(n log n)

Full Transcript

This visualization shows the divide and conquer method to find the maximum subarray sum. The array is split into halves recursively until single elements are reached. At each step, the maximum subarray sum is found for the left half, right half, and the subarray crossing the middle. The maximum of these three is returned. The execution table tracks these steps with subarray ranges and sums. The variable tracker shows how max sums change. Key moments clarify why crossing sums are needed and how base cases work. The quiz tests understanding of these steps and results.