Find Maximum Subarray Divide and Conquer in DSA Javascript - 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 as result

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

Execution Sample

DSA Javascript

function maxCrossingSubarray(arr, left, mid, right) {
  let leftSum = Number.NEGATIVE_INFINITY;
  let sum = 0;
  for (let i = mid; i >= left; i--) {
    sum += arr[i];
    leftSum = Math.max(leftSum, sum);
  }
  let rightSum = Number.NEGATIVE_INFINITY;
  sum = 0;
  for (let i = mid + 1; i <= right; i++) {
    sum += arr[i];
    rightSum = Math.max(rightSum, sum);
  }
  return leftSum + rightSum;
}

function maxSubArray(arr, left, right) {
  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);
}

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

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 single element	[0..0]	1	-	-	1	[1]
5	Divide single element	[1..1]	-3	-	-	-3	[-3]
6	Find cross max [0..1]	[0..1]	1	-3	-2	1	[1, -3]
7	Return max left half [0..1]	[0..1]	1	-3	-2	1	[1, -3]
8	Divide right half	[2..2]	-	-	-	2	[2]
9	Find cross max [0..2]	[0..2]	1	2	0	2	[1, -3, 2]
10	Return max left half [0..2]	[0..2]	2	-	-	2	[1, -3, 2]
11	Divide right half of full array	[3..4]	-	-	-	-	[1, -1]
12	Divide single element	[3..3]	1	-	-	1	[1]
13	Divide single element	[4..4]	-1	-	-	-1	[-1]
14	Find cross max [3..4]	[3..4]	1	-1	0	1	[1, -1]
15	Return max right half [3..4]	[3..4]	1	-1	0	1	[1, -1]
16	Find cross max full array [0..4]	[0..4]	2	1	3	3	[1, -3, 2, 1, -1]
17	Return max full array [0..4]	[0..4]	2	1	3	3	[1, -3, 2, 1, -1]
18	End recursion	-	-	-	-	-	[Max subarray sum = 3]

💡 Recursion ends when subarray size is 1; max subarray sums are combined and compared.

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 6	After Step 8	After Step 12	After Step 14	After Step 16	Final
left	0	0	0	0	2	3	3	0	0
right	4	1	1	1	2	4	4	4	4
mid	-	0	0	0	2	3	3	2	-
leftMax	-	1	1	1	2	1	1	2	3
rightMax	-	-	-	-	-	-	1	1	3
crossMax	-	-	-2	-2	-	0	0	3	3

Key Moments - 3 Insights

Why do we check the cross max subarray separately?

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

Why does recursion stop when left equals right?

At that point, the subarray has only one element, so the max subarray sum is that element itself (see steps 4, 5, 8, 12, 13).

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

We take the maximum of the three sums to find the overall max subarray sum for the current range (see steps 7, 10, 15, 17).

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the crossMax value?

A 3

B 0

C 1

D -2

💡 Hint

Check the 'Cross Max' column in row with Step 9.

At which step does the recursion first return a max subarray sum of 1?

A Step 4

B Step 5

C Step 6

D Step 8

💡 Hint

Look at the 'Max Returned' column and find when it first shows 1.

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

A It would always be zero

B It would be the sum of the entire array

C It would be the least negative single element

D It would be the most negative sum crossing middle

💡 Hint

Recall that max subarray for all negatives is the largest single element (see variable_tracker for leftMax and rightMax).

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
Cross max checks subarray crossing midpoint
Time complexity ~ O(n log n)

Full Transcript

This visualization shows how the divide and conquer method finds the maximum subarray sum. The array is split into halves until single elements remain. Then, max subarrays are found in left half, right half, and crossing the middle. The maximum of these three is returned up the recursion. The execution table tracks these steps with subarray ranges and max sums. Key moments clarify why crossing sums are needed and when recursion stops. The variable tracker shows how left, right, mid, and max sums change. Quizzes test understanding of cross max values, recursion returns, and behavior with negative numbers.

Practice

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

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 sum

C. Use a sliding window to find the max sum by expanding and shrinking the window

D. Calculate the sum of all elements and return it as the max subarray sum

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 subproblems

   Find max subarray in left half, right half, and crossing the middle, then take the maximum of these three.

3. Final Answer:

   Split array, find max left, right, and crossing sums, then combine -> Option A

4. Quick Check:

   Divide and conquer = split and combine max sums [OK]

Hint: Remember: divide array, conquer halves, combine max sums [OK]

Common Mistakes:

• Thinking sorting helps find max subarray sum
• Ignoring the crossing middle subarray
• Assuming max subarray is always the largest single element

2. Which of the following is the correct base case condition in a divide and conquer function to find the maximum subarray?

easy

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

B. If the array length is 0, return 0

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

D. If the array length is 1, return 0

Solution

1. Step 1: Identify base case for recursion

   When the array has only one element, that element itself is the max subarray sum.

2. Step 2: Return the single element value

   Return the element value directly as the max sum for that subarray.

3. Final Answer:

   Return the single element when array length is 1 -> Option A

4. Quick Check:

   Base case single element = element value [OK]

Hint: Base case: single element array returns that element [OK]

Common Mistakes:

• Returning 0 instead of the element for single element array
• Returning sum of two elements as base case
• Not defining a base case causing infinite recursion

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

function maxCrossingSum(arr, left, mid, right) {
  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. 9

B. 7

C. 3

D. 5

Solution

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

   Starting at index 2 (value 3), sum = 3; then index 1 (-1), sum=2; index 0 (2), sum=4. Max leftSum = 4.

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

   Starting at index 3 (-4), sum = -4; index 4 (5), sum=1. Max rightSum = 1.

3. Step 3: Add leftSum and rightSum

   4 + 1 = 5.

4. Final Answer:

   5 -> Option D

5. Quick Check:

   Left max 4 + Right max 1 = 5 [OK]

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

Common Mistakes:

• Adding wrong subarray sums crossing mid
• Mixing indices for left and right sums
• Using max element instead of max crossing sum

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

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

medium

A. The base case should return 0 instead of arr[left]

B. The left recursive call should be maxSubArray(arr, left, mid)

C. The right recursive call should be maxSubArray(arr, mid, right)

D. The mid calculation is incorrect

Solution

1. Step 1: Check recursive calls range

   Left recursive call uses mid - 1, which excludes mid element incorrectly.

2. Step 2: Correct left recursive call to include mid

   Change left recursive call to maxSubArray(arr, left, mid) to include mid element.

3. Final Answer:

   Left recursive call should be maxSubArray(arr, left, mid) -> Option B

4. Quick Check:

   Include mid in left recursion [OK]

Hint: Include mid index in left recursion call [OK]

Common Mistakes:

• Excluding mid element in recursive calls
• Returning 0 instead of element in base case
• Incorrect mid calculation causing infinite recursion

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

hard

A. 7

B. 5

C. 6

D. 4

Solution

1. Step 1: Identify the max subarray

   The subarray [4, -1, 2, 1] (indices 3-6) sums to 4 + (-1) + 2 + 1 = 6.

2. Step 2: Check extending right

   [4, -1, 2, 1, -5] = 1 < 6; [4, -1, 2, 1, -5, 4] = 5 < 6.

3. Step 3: Check extending left

   [-3, 4, -1, 2, 1] = 3 < 6; further left smaller.

4. Final Answer:

   6 -> Option C

5. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Check sums of all subarrays crossing mid carefully [OK]

Common Mistakes:

• Miscomputing as 7 by skipping the -3
• Choosing sum 5 by including the end
• Picking single largest element 4