Find Maximum Subarray Divide and Conquer in DSA Typescript - Build from Scratch

Find Maximum Subarray using Divide and Conquer

📖 Scenario: Imagine you are analyzing daily temperature changes over a week. You want to find the longest period where the temperature rise was the highest overall. This is like finding the maximum sum of a continuous subarray in a list of numbers.

🎯 Goal: You will build a program that uses the divide and conquer method to find the maximum sum of a continuous subarray in a given array of numbers.

📋 What You'll Learn

Create an array called nums with the exact values [2, -4, 3, -1, 5, -6, 1, 4]

Create a helper function called maxCrossingSum that finds the maximum sum crossing the middle of the array

Create a recursive function called maxSubArraySum that uses divide and conquer to find the maximum subarray sum

Print the maximum subarray sum found by maxSubArraySum

💡 Why This Matters

🌍 Real World

Finding maximum subarray sums helps in financial analysis to find the best time to buy and sell stocks for maximum profit.

💼 Career

Understanding divide and conquer algorithms is essential for software engineers working on performance-critical applications and algorithm design.

1

Create the array of numbers

Create an array called nums with these exact values: [2, -4, 3, -1, 5, -6, 1, 4]

DSA Typescript

// Create the array nums with the given values
// Your code here

Hint

Use const nums: number[] = [2, -4, 3, -1, 5, -6, 1, 4]; to create the array.

2

Create the maxCrossingSum helper function

Create a function called maxCrossingSum that takes arr: number[], left: number, mid: number, and right: number as parameters and returns the maximum sum of a subarray crossing the middle index.

DSA Typescript

const nums: number[] = [2, -4, 3, -1, 5, -6, 1, 4];

// Create maxCrossingSum function below
// Your code here

Hint

Use two loops: one going left from mid, one going right from mid+1, to find max sums, then add them.

3

Create the maxSubArraySum recursive function

Create a recursive function called maxSubArraySum that takes arr: number[], left: number, and right: number as parameters and returns the maximum subarray sum using divide and conquer. Use maxCrossingSum inside it.

DSA Typescript

const nums: number[] = [2, -4, 3, -1, 5, -6, 1, 4];

function maxCrossingSum(arr: number[], left: number, mid: number, right: number): number {
    let sum = 0;
    let leftSum = Number.NEGATIVE_INFINITY;
    for (let i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > leftSum) leftSum = sum;
    }
    sum = 0;
    let rightSum = Number.NEGATIVE_INFINITY;
    for (let i = mid + 1; i  rightSum) rightSum = sum;
    }
    return leftSum + rightSum;
}

// Create maxSubArraySum function below
// Your code here

Hint

Divide the array into two halves, find max subarray sum in left, right, and crossing middle, then return the max.

4

Print the maximum subarray sum

Use console.log to print the result of calling maxSubArraySum with nums, 0, and nums.length - 1 as arguments.

DSA Typescript

const nums: number[] = [2, -4, 3, -1, 5, -6, 1, 4];

function maxCrossingSum(arr: number[], left: number, mid: number, right: number): number {
    let sum = 0;
    let leftSum = Number.NEGATIVE_INFINITY;
    for (let i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > leftSum) leftSum = sum;
    }
    sum = 0;
    let rightSum = Number.NEGATIVE_INFINITY;
    for (let i = mid + 1; i  rightSum) rightSum = sum;
    }
    return leftSum + rightSum;
}

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

// Print the maximum subarray sum
// Your code here

Hint

Call maxSubArraySum(nums, 0, nums.length - 1) and print the result using console.log.

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