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.

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