Find Maximum Subarray Divide and Conquer in DSA Javascript

Mental Model

Split the array into halves, find the best subarray in left, right, and crossing the middle, then pick the best among them.

Analogy: Imagine you want to find the richest part of a street. You check the left side, the right side, and the middle area where both sides meet, then choose the richest spot overall.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Split: [ -2, 1, -3, 4, -1 ] | [ 2, 1, -5, 4 ]
Middle: between -1 and 2
Pointers: left half ↑, right half ↑, middle ↑

Dry Run Walkthrough

Input: array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Goal: Find the maximum sum of any contiguous subarray using divide and conquer

Step 1: Split array into left [-2,1,-3,4,-1] and right [2,1,-5,4]

Left: [-2,1,-3,4,-1] | Right: [2,1,-5,4]

Why: Divide problem into smaller parts to solve recursively

Step 2: Find max subarray in left half recursively

Left max subarray found: [4] with sum 4

Why: Find best subarray in left half

Step 3: Find max subarray in right half recursively

Right max subarray found: [4] with sum 4

Why: Find best subarray in right half

Step 4: Find max crossing subarray crossing middle

Crossing max subarray: [4,-1,2,1] with sum 6

Why: Check subarrays crossing the middle for max sum

Step 5: Compare left max (4), right max (4), crossing max (6) and pick max

Max subarray is crossing: [4,-1,2,1] sum 6

Why: Final answer is the maximum among three candidates

Result:

Max subarray: 4 -> -1 -> 2 -> 1 with sum 6

Annotated Code

DSA Javascript

class Result {
  constructor(leftSum, rightSum, maxSum, totalSum) {
    this.leftSum = leftSum;
    this.rightSum = rightSum;
    this.maxSum = maxSum;
    this.totalSum = totalSum;
  }
}

function maxSubArrayDivideAndConquer(nums) {
  function helper(left, right) {
    if (left === right) {
      // Base case: single element
      return new Result(nums[left], nums[left], nums[left], nums[left]);
    }

    const mid = Math.floor((left + right) / 2);
    const leftResult = helper(left, mid);
    const rightResult = helper(mid + 1, right);

    // Combine results
    const totalSum = leftResult.totalSum + rightResult.totalSum;
    const leftSum = Math.max(leftResult.leftSum, leftResult.totalSum + rightResult.leftSum);
    const rightSum = Math.max(rightResult.rightSum, rightResult.totalSum + leftResult.rightSum);
    const maxSum = Math.max(leftResult.maxSum, rightResult.maxSum, leftResult.rightSum + rightResult.leftSum);

    return new Result(leftSum, rightSum, maxSum, totalSum);
  }

  if (nums.length === 0) return 0;
  return helper(0, nums.length - 1).maxSum;
}

// Driver code
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArrayDivideAndConquer(nums));

if (left === right) { return new Result(nums[left], nums[left], nums[left], nums[left]); }

Base case: single element forms all sums

const mid = Math.floor((left + right) / 2);

Find middle index to split array

const leftResult = helper(left, mid);

Recursively find max subarray info in left half

const rightResult = helper(mid + 1, right);

Recursively find max subarray info in right half

const totalSum = leftResult.totalSum + rightResult.totalSum;

Total sum of current segment is sum of left and right

const leftSum = Math.max(leftResult.leftSum, leftResult.totalSum + rightResult.leftSum);

Max sum starting from left edge of segment

const rightSum = Math.max(rightResult.rightSum, rightResult.totalSum + leftResult.rightSum);

Max sum ending at right edge of segment

const maxSum = Math.max(leftResult.maxSum, rightResult.maxSum, leftResult.rightSum + rightResult.leftSum);

Max subarray sum in segment: left max, right max, or crossing middle

return new Result(leftSum, rightSum, maxSum, totalSum);

Return combined result for current segment

Output

6

Complexity Analysis

Time: O(n log n) because the array is split into halves recursively and each merge step takes constant time

Space: O(log n) due to recursion stack depth for dividing the array

vs Alternative: Compared to Kadane's O(n) approach, divide and conquer is slower but shows a clear recursive strategy

Edge Cases

empty array

returns 0 as no subarray exists

DSA Javascript

if (nums.length === 0) return 0;

array with one element

returns that element as max subarray sum

DSA Javascript

if (left === right) { return new Result(nums[left], nums[left], nums[left], nums[left]); }

all negative numbers

returns the largest (least negative) single element

DSA Javascript

base case returns single element sums

When to Use This Pattern

When asked to find maximum sum of contiguous subarray and recursion or divide and conquer is allowed, use this pattern to split and combine results efficiently.

Common Mistakes

Mistake: Not correctly combining left and right results for crossing subarray sums
Fix: Calculate max crossing sum as leftResult.rightSum + rightResult.leftSum and compare with left and right max sums

Mistake: Forgetting to handle base case of single element
Fix: Return a Result object with all sums equal to that element when left equals right

Summary

Finds the maximum sum of any contiguous subarray using divide and conquer.

Use when you want a recursive approach that splits the problem into halves.

The key insight is to consider max subarrays in left, right, and crossing the middle.

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