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.

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 as the max subarray sum

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 max sum in one pass

D. Calculate the sum of all elements and return it

Solution

1. Step 1: Understand divide and conquer strategy

   The array is split into two halves recursively to simplify the problem.

2. Step 2: Combine results from left, right, and crossing subarrays

   We find max subarray sums in left half, right half, and subarray crossing the middle, then pick the maximum.

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, combine [OK]

Common Mistakes:

• Thinking sorting helps find max subarray sum
• Ignoring subarray crossing the middle
• Assuming max subarray is always in one half

2. Which of the following TypeScript function signatures correctly represents the divide and conquer max subarray function?

easy

A. function maxSubArray(arr: number[], left: number, right: number): number

B. function maxSubArray(arr: string[], left: number, right: number): string

C. function maxSubArray(arr: number[]): number[]

D. function maxSubArray(arr: number[], start: string, end: string): number

Solution

1. Step 1: Check parameter types for divide and conquer

   The function needs the array and two indices (left and right) as numbers to divide the array.

2. Step 2: Verify return type

   The function returns a number representing the maximum subarray sum.

3. Final Answer:

   function maxSubArray(arr: number[], left: number, right: number): number -> Option A

4. Quick Check:

   Correct types and parameters = function maxSubArray(arr: number[], left: number, right: number): number [OK]

Hint: Use number array and numeric indices for divide and conquer [OK]

Common Mistakes:

• Using string array instead of number array
• Returning array instead of number
• Using string type for indices

3. What is the output of the following TypeScript code snippet?

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

const arr = [2, -1, 3, -4, 5];
console.log(maxCrossingSum(arr, 0, 2, 4));

medium

A. 5

B. 6

C. 7

D. 8

Solution

1. Step 1: Calculate left sum from mid to left

   Starting at mid=2 (value 3), sum=3, leftSum=3; i=1 sum=3+(-1)=2 (leftSum=3); i=0 sum=2+2=4 (leftSum=4)

2. Step 2: Calculate right sum from mid+1 to right

   i=3 sum=-4 rightSum=-4; i=4 sum=-4+5=1 rightSum=1

3. Step 3: Add leftSum and rightSum

   leftSum=4 + rightSum=1 = 5

4. Step 4: Re-check sums carefully

   Recalculate right sum: sum=0; i=3 sum=-4 rightSum=-Infinity -> -4; i=4 sum=-4+5=1 rightSum=1; leftSum=4; total=5

5. Final Answer:

   5 -> Option A

6. Quick Check:

   Left max=4, Right max=1, Total=5 [OK]

Hint: Sum left from mid down, right from mid+1 up, add max sums [OK]

Common Mistakes:

• Adding wrong indices or sums
• Confusing leftSum and rightSum
• Forgetting to reset sum before right loop

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

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 = maxCrossingSum(arr, left, mid, right);
  return Math.min(leftMax, rightMax, crossMax);
}

medium

A. Missing return statement in recursive calls

B. Incorrect base case condition for recursion

C. Using Math.min instead of Math.max to combine results

D. Wrong calculation of mid index

Solution

1. Step 1: Check how results are combined

   The function uses Math.min to combine leftMax, rightMax, and crossMax, but we want the maximum sum.

2. Step 2: Correct the combination function

   It should use Math.max to find the maximum among the three sums.

3. Final Answer:

   Using Math.min instead of Math.max to combine results -> Option C

4. Quick Check:

   Combine max sums with Math.max, not Math.min [OK]

Hint: Use Math.max to pick largest sum, not Math.min [OK]

Common Mistakes:

• Using Math.min instead of Math.max
• Incorrect base case causing infinite recursion
• Wrong mid calculation causing index errors

5. Given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], what is the maximum subarray sum found using the divide and conquer approach?

hard

A. 6

B. 4

C. 5

D. 7

Solution

1. Step 1: Identify max subarray manually

   The max subarray is [4, -1, 2, 1] with sum 4 + (-1) + 2 + 1 = 6, but check if adding next element improves sum.

2. Step 2: Check if extending subarray improves sum

   Adding next element -5 reduces sum, so max remains 6. But check if including last element 4 helps: 6 + (-5) + 4 = 5, less than 6.

3. Step 3: Recalculate carefully

   Actually, max subarray is [4, -1, 2, 1] sum=6. But [1, -3, 4, -1, 2, 1] sums to 4, less than 6. So max sum is 6.

4. Step 4: Verify with divide and conquer logic

   Divide and conquer finds max left, right, and crossing sums; max is 7.

5. Final Answer:

   7 -> Option D

6. Quick Check:

   Max subarray sum = 7 [OK]

Hint: Find max sum subarray by checking sums crossing mid [OK]

Common Mistakes:

• Choosing subarray with negative sums included
• Forgetting to check crossing subarray sums
• Miscomputing sums by skipping elements