Find Maximum Subarray Divide and Conquer in DSA Typescript - 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 max of three

↓

If array size is 1, return that element as max

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

Execution Sample

DSA Typescript

function maxSubArray(arr: number[], left: number, right: number): number {
  if (left === right) return arr[left];
  const mid = Math.floor((left + right) / 2);
  const leftMax = maxSubArray(arr, left, mid);
  const rightMax = maxSubArray(arr, mid + 1, right);
  const crossMax = maxCrossingSubarray(arr, left, mid, right);
  return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossingSubarray(arr: number[], left: number, mid: number, right: number): number {
  let leftSum = -Infinity;
  let sum = 0;
  for (let i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > leftSum) leftSum = sum;
  }
  let rightSum = -Infinity;
  sum = 0;
  for (let i = mid + 1; i <= right; i++) {
    sum += arr[i];
    if (sum > rightSum) rightSum = sum;
  }
  return leftSum + rightSum;
}

const arr = [1, -3, 2, 1, -1];
console.log(maxSubArray(arr, 0, arr.length - 1)); // Output: 3

This code finds the maximum subarray sum in arr between left and right using divide and conquer. Includes the maxCrossingSubarray helper function.

Execution Table

Step	Operation	Subarray Range	Left Max	Right Max	Cross Max	Max Returned	Visual State
1	Divide full array	[0..4]	-	-	-	-	[1, -3, 2, 1, -1]
2	Divide left half	[0..2]	-	-	-	-	[1, -3, 2]
3	Divide left-left half	[0..1]	-	-	-	-	[1, -3]
4	Divide left-left-left half	[0..0]	1	-	-	1	[1]
5	Divide left-left-right half	[1..1]	-3	-	-	-3	[-3]
6	Find crossing max for [0..1]	-	-	-	-2	-2	[1, -3]
7	Max of left-left halves	-	1	-3	-2	1	[1, -3]
8	Divide left-right half	[2..2]	2	-	-	2	[2]
9	Find crossing max for [0..2]	-	-	-	3	3	[1, -3, 2]
10	Max of left half	-	1	2	3	3	[1, -3, 2]
11	Divide right half	[3..4]	-	-	-	-	[1, -1]
12	Divide right-left half	[3..3]	1	-	-	1	[1]
13	Divide right-right half	[4..4]	-1	-	-	-1	[-1]
14	Find crossing max for [3..4]	-	-	-	0	0	[1, -1]
15	Max of right half	-	1	-1	0	1	[1, -1]
16	Find crossing max for full array	-	-	-	3	3	[1, -3, 2, 1, -1]
17	Max of full array	-	3	1	3	3	[1, -3, 2, 1, -1]
18	Return final max	-	-	-	-	3	[1, -3, 2, 1, -1]

💡 Recursion ends when subarray size is 1 (left == right), returning that element.

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 7	After Step 8	After Step 10	After Step 15	After Step 17	Final
left	0	0	0	0	2	0	3	0	0
right	4	1	1	1	2	2	4	4	4
mid	-	0	0	0	2	1	3	2	2
leftMax	-	1	1	1	2	3	1	3	3
rightMax	-	-3	-3	-3	-	-	1	1	1
crossMax	-	-	-2	-2	-	3	0	3	3

Key Moments - 3 Insights

Why do we return arr[left] when left equals right?

Because the subarray has only one element, so that element is the max subarray sum. See execution_table step 4 where left == right == 0 returns 1.

How is the crossing max subarray found and why is it important?

Crossing max sums subarrays crossing the middle point. It combines max sums from left and right sides around mid. See execution_table steps 6, 9, 14, and 16 where crossMax is calculated and compared.

Why do we compare leftMax, rightMax, and crossMax?

Because the max subarray can be fully in left half, right half, or crossing the middle. We must pick the largest among these three. See execution_table steps 7, 10, 15, and 17.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the max subarray sum for the left half [0..2]?

A 3

B 1

C 2

D -2

💡 Hint

Check the 'Max Returned' column at step 10 in execution_table.

At which step does the recursion return the max subarray sum for the single element subarray [1..1]?

A Step 4

B Step 5

C Step 12

D Step 13

💡 Hint

Look for the step where subarray range is [1..1] and max returned is -3.

If the array had all negative numbers, how would the max subarray sum change in the execution_table?

A It would be the sum of all elements

B It would be zero

C It would be the least negative single element

D It would be the crossing max only

💡 Hint

Recall that maxSubArray returns single elements when subarray size is 1, so max sum is max single element.

Concept Snapshot

Divide array into halves recursively
Find max subarray in left, right, and crossing middle
Return max of these three
Base case: single element subarray returns that element
Crossing max combines left and right sums around mid
Overall max is largest among leftMax, rightMax, crossMax

Full Transcript

The divide and conquer method for finding the maximum subarray splits the array into two halves. It recursively finds the maximum subarray sum in the left half, right half, and also finds the maximum subarray that crosses the middle point. The base case occurs when the subarray has only one element, which is returned as the max sum. After computing the left max, right max, and crossing max, the algorithm returns the largest of these three values. This process continues until the entire array is processed, resulting in the maximum subarray sum. The execution table shows each recursive step, the subarray ranges, and the max sums found. The variable tracker follows key variables like left, right, mid, and the max sums at each step. Key moments clarify why the base case returns a single element, the importance of crossing max, and why all three max values are compared. The visual quiz tests understanding of these steps and outcomes.