Why Find Maximum Subarray Divide and Conquer in DSA Typescript?

The Big Idea

Discover how breaking a big problem into smaller pieces can save you hours of work!

The Scenario

Imagine you have a long list of daily profits and losses for your small business. You want to find the best period where you made the most money overall. Doing this by checking every possible period by hand would take forever!

The Problem

Manually checking every possible start and end day to find the best profit period is very slow and tiring. It's easy to make mistakes, miss some periods, or get confused by all the numbers.

The Solution

The divide and conquer method breaks the big problem into smaller parts, solves each part, and then combines the answers. This way, it quickly finds the best profit period without checking every possibility one by one.

Before vs After

✗ Before

function maxSubarrayBruteForce(arr: number[]): number {
  let maxSum = -Infinity;
  for (let start = 0; start < arr.length; start++) {
    for (let end = start; end < arr.length; end++) {
      let sum = 0;
      for (let k = start; k <= end; k++) {
        sum += arr[k];
      }
      if (sum > maxSum) maxSum = sum;
    }
  }
  return maxSum;
}

✓ After

function maxSubarrayDivideAndConquer(arr: number[], left: number, right: number): number {
  if (left === right) return arr[left];
  const mid = Math.floor((left + right) / 2);
  const leftMax = maxSubarrayDivideAndConquer(arr, left, mid);
  const rightMax = maxSubarrayDivideAndConquer(arr, mid + 1, right);
  let leftSum = -Infinity, 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 Math.max(leftMax, rightMax, leftSum + rightSum);
}

What It Enables

This method lets you quickly find the most profitable period in a list of numbers, even if the list is very long.

Real Life Example

Financial analysts use this to find the best time to buy and sell stocks by identifying the period with the highest gain.

Key Takeaways

Manual checking is slow and error-prone for large lists.

Divide and conquer breaks the problem into smaller parts and combines results efficiently.

This method finds the maximum subarray sum faster and more reliably.

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