Find Maximum Subarray Divide and Conquer in DSA Typescript

Mental Model

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

Analogy: Imagine cutting a chocolate bar into two parts, finding the best piece on the left, the best on the right, and the best piece that crosses the cut, then choosing the tastiest piece overall.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Split: [ -2, 1, -3, 4, -1 ] | [ 2, 1, -5, 4 ]
Left max subarray [4] ↑
Right max subarray [4] ↑
Cross max subarray [4, -1, 2, 1] ↑

Dry Run Walkthrough

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

Goal: Find the maximum sum of any continuous 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: [4] with sum 4

Why: Find max subarray in left part

Step 3: Find max subarray in right half recursively

Right max subarray: [4] with sum 4

Why: Find max subarray in right part

Step 4: Find max subarray crossing middle between left and right halves

Cross 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), and cross max (6), choose max

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

Why: Final max subarray is the best among left, right, and crossing

Result:

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

Annotated Code

DSA Typescript

class MaxSubarray {
  static findMaxCrossingSubarray(arr: number[], low: number, mid: number, high: number): {maxSum: number, leftIndex: number, rightIndex: number} {
    let leftSum = Number.NEGATIVE_INFINITY;
    let sum = 0;
    let maxLeft = mid;
    for (let i = mid; i >= low; i--) {
      sum += arr[i];
      if (sum > leftSum) {
        leftSum = sum;
        maxLeft = i;
      }
    }

    let rightSum = Number.NEGATIVE_INFINITY;
    sum = 0;
    let maxRight = mid + 1;
    for (let j = mid + 1; j <= high; j++) {
      sum += arr[j];
      if (sum > rightSum) {
        rightSum = sum;
        maxRight = j;
      }
    }

    return { maxSum: leftSum + rightSum, leftIndex: maxLeft, rightIndex: maxRight };
  }

  static findMaxSubarray(arr: number[], low: number, high: number): {maxSum: number, leftIndex: number, rightIndex: number} {
    if (low === high) {
      return { maxSum: arr[low], leftIndex: low, rightIndex: high };
    }

    const mid = Math.floor((low + high) / 2);

    const leftResult = this.findMaxSubarray(arr, low, mid);
    const rightResult = this.findMaxSubarray(arr, mid + 1, high);
    const crossResult = this.findMaxCrossingSubarray(arr, low, mid, high);

    if (leftResult.maxSum >= rightResult.maxSum && leftResult.maxSum >= crossResult.maxSum) {
      return leftResult;
    } else if (rightResult.maxSum >= leftResult.maxSum && rightResult.maxSum >= crossResult.maxSum) {
      return rightResult;
    } else {
      return crossResult;
    }
  }
}

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const result = MaxSubarray.findMaxSubarray(arr, 0, arr.length - 1);
console.log(`Max subarray: [${arr.slice(result.leftIndex, result.rightIndex + 1).join(", ")}] with sum ${result.maxSum}`);

for (let i = mid; i >= low; i--) { sum += arr[i]; if (sum > leftSum) { leftSum = sum; maxLeft = i; } }

Find max sum subarray ending at mid going left

for (let j = mid + 1; j <= high; j++) { sum += arr[j]; if (sum > rightSum) { rightSum = sum; maxRight = j; } }

Find max sum subarray starting at mid+1 going right

if (low === high) { return { maxSum: arr[low], leftIndex: low, rightIndex: high }; }

Base case: single element subarray

const mid = Math.floor((low + high) / 2);

Divide array into two halves

const leftResult = this.findMaxSubarray(arr, low, mid);

Recursively find max subarray in left half

const rightResult = this.findMaxSubarray(arr, mid + 1, high);

Recursively find max subarray in right half

const crossResult = this.findMaxCrossingSubarray(arr, low, mid, high);

Find max subarray crossing the middle

Compare leftResult.maxSum, rightResult.maxSum, crossResult.maxSum and return the max

Choose the best max subarray among left, right, and crossing

Output

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

Complexity Analysis

Time: O(n log n) because the array is split into halves recursively and each merge step takes O(n) to find crossing max

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

vs Alternative: Better than naive O(n^2) approach that checks all subarrays, but slower than Kadane's O(n) linear scan

Edge Cases

Array with single element

Returns that element as max subarray

DSA Typescript

if (low === high) { return { maxSum: arr[low], leftIndex: low, rightIndex: high }; }

Array with all negative numbers

Returns the least negative single element as max subarray

DSA Typescript

if (low === high) { return { maxSum: arr[low], leftIndex: low, rightIndex: high }; }

Array with multiple max subarrays of same sum

Returns one of the max subarrays found by divide and conquer

DSA Typescript

Compare leftResult.maxSum, rightResult.maxSum, crossResult.maxSum and return the max

When to Use This Pattern

When asked to find maximum sum of a continuous subarray and you want a divide and conquer approach, use this pattern to split and combine results efficiently.

Common Mistakes

Mistake: Not correctly handling the crossing subarray that spans both halves
Fix: Implement a separate function to find max crossing subarray by expanding from middle to left and right

Mistake: Forgetting base case of single element leading to infinite recursion
Fix: Add base case to return single element subarray when low equals high

Summary

Finds the maximum sum continuous subarray using divide and conquer.

Use when you want a recursive approach splitting the array into halves.

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