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.