Find Maximum Subarray Divide and Conquer in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Subarray Sum Using Divide and Conquer

What is the output of the following TypeScript code that finds the maximum subarray sum using divide and conquer?

DSA Typescript

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 <= right; i++) {
    sum += arr[i];
    if (sum > 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);
}

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArraySum(arr, 0, arr.length - 1));

A 6

B 7

C 5

D 4

💡 Hint

Think about the subarray with the largest sum that crosses the middle point.

The maximum subarray is [4, -1, 2, 1] which sums to 6.

🧠 Conceptual

intermediate

Understanding the Divide and Conquer Approach for Maximum Subarray

In the divide and conquer method for finding the maximum subarray, which of the following best describes the role of the 'crossing sum'?

A It finds the maximum sum subarray that lies entirely in the right half.

B It finds the maximum sum subarray that crosses the midpoint dividing the array into two halves.

C It finds the maximum sum subarray that lies entirely in the left half.

D It finds the minimum sum subarray crossing the midpoint.

💡 Hint

Think about subarrays that include elements from both halves.

The crossing sum specifically looks for the maximum subarray that includes elements from both sides of the midpoint.

🔧 Debug

advanced

Identify the Error in Maximum Subarray Divide and Conquer Code

What error will the following TypeScript code produce when executed?

DSA Typescript

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 <= right; i++) {
    sum += arr[i];
    if (sum > 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);
}

const arr = [];
console.log(maxSubArraySum(arr, 0, arr.length - 1));

A RangeError: Invalid array length

B TypeError: Cannot read property '0' of undefined

C RangeError: Maximum call stack size exceeded

D RangeError: Invalid array index

💡 Hint

Consider what happens when the input array is empty.

The recursive function calls itself with invalid indices causing infinite recursion and stack overflow.

❓ Predict Output

advanced

Resulting Maximum Subarray Sum for Negative Numbers

What is the output of the following code that finds the maximum subarray sum using divide and conquer on an array of all negative numbers?

DSA Typescript

const arr = [-8, -3, -6, -2, -5, -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 <= right; i++) {
    sum += arr[i];
    if (sum > 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);
}

console.log(maxSubArraySum(arr, 0, arr.length - 1));

A -2

B -3

C -4

D -5

💡 Hint

The maximum subarray in all negative numbers is the least negative single element.

The maximum subarray is [-2] with sum -2, which is the largest among all negative numbers.

🚀 Application

expert

Maximum Subarray Sum with Indices Using Divide and Conquer

Given the divide and conquer approach, which option correctly returns the maximum subarray sum along with the start and end indices of that subarray?

DSA Typescript

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

function maxSubArraySum(arr: number[], left: number, right: number): {maxSum: number, start: number, end: number} {
  if (left === right) return {maxSum: arr[left], start: left, end: right};
  const mid = Math.floor((left + right) / 2);
  const leftResult = maxSubArraySum(arr, left, mid);
  const rightResult = maxSubArraySum(arr, mid + 1, right);
  const crossResult = maxCrossingSum(arr, left, mid, right);
  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 = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7];
console.log(maxSubArraySum(arr, 0, arr.length - 1));

A {"maxSum":50,"start":7,"end":11}

B {"maxSum":48,"start":0,"end":3}

C {"maxSum":43,"start":3,"end":10}

D {"maxSum":43,"start":7,"end":10}

💡 Hint

Check the subarray with the largest sum and its indices carefully.

The maximum subarray is [18, 20, -7, 12] from index 7 to 10 with sum 43.

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