Find Maximum Subarray Divide and Conquer in DSA Javascript - 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 JavaScript code that finds the maximum subarray sum using divide and conquer?

DSA Javascript

function maxCrossingSum(arr, left, mid, right) {
  let sum = 0;
  let left_sum = -Infinity;
  for (let i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > left_sum) left_sum = sum;
  }
  sum = 0;
  let right_sum = -Infinity;
  for (let i = mid + 1; i <= right; i++) {
    sum += arr[i];
    if (sum > right_sum) right_sum = sum;
  }
  return left_sum + right_sum;
}

function maxSubArraySum(arr, left, right) {
  if (left === right) return arr[left];
  let mid = Math.floor((left + right) / 2);
  let left_max = maxSubArraySum(arr, left, mid);
  let right_max = maxSubArraySum(arr, mid + 1, right);
  let cross_max = maxCrossingSum(arr, left, mid, right);
  return Math.max(left_max, right_max, cross_max);
}

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 in the array [-2, 1, -3, 4, -1, 2, 1, -5, 4].

The maximum subarray is [4, -1, 2, 1] which sums to 6. The divide and conquer approach finds this by checking left, right, and crossing sums recursively.

🧠 Conceptual

intermediate

Understanding the Divide and Conquer Approach for Maximum Subarray

Which of the following best describes the role of the 'maxCrossingSum' function in the divide and conquer algorithm for finding the maximum subarray?

A It finds the maximum subarray sum only in the right half of the array.

B It finds the maximum subarray sum only in the left half of the array.

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

D It finds the maximum subarray sum by checking all possible subarrays in the array.

💡 Hint

Consider what happens when the maximum subarray crosses the midpoint.

The 'maxCrossingSum' function calculates the maximum sum of a subarray that crosses the midpoint, combining elements from both halves.

🔧 Debug

advanced

Identify the Error in Maximum Subarray Divide and Conquer Implementation

What error will occur when running the following code snippet for maximum subarray sum using divide and conquer?

DSA Javascript

function maxCrossingSum(arr, left, mid, right) {
  let sum = 0;
  let left_sum = -Infinity;
  for (let i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > left_sum) left_sum = sum;
  }
  sum = 0;
  let right_sum = -Infinity;
  for (let i = mid + 1; i <= right; i++) {
    sum += arr[i];
    if (sum > right_sum) right_sum = sum;
  }
  return left_sum + right_sum;
}

function maxSubArraySum(arr, left, right) {
  if (left > right) return 0;
  if (left === right) return arr[left];
  let mid = Math.floor((left + right) / 2);
  let left_max = maxSubArraySum(arr, left, mid);
  let right_max = maxSubArraySum(arr, mid + 1, right);
  let cross_max = maxCrossingSum(arr, left, mid, right);
  return Math.max(left_max, right_max, cross_max);
}

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

A The base case 'if (left > right) return 0;' causes incorrect results for arrays with all negative numbers.

B The function maxCrossingSum returns the wrong sum because it does not include the midpoint element.

C The code throws a TypeError because of invalid array indexing.

D The recursion never ends because the base case is missing.

💡 Hint

Think about what happens when all numbers are negative and the base case returns 0.

Returning 0 when left > right causes the algorithm to consider empty subarrays, which can lead to incorrect maximum sums when all elements are negative.

📝 Syntax

advanced

Syntax Error in Maximum Subarray Divide and Conquer Code

Which option contains a syntax error that will prevent the maximum subarray divide and conquer code from running?

A

function maxSubArraySum(arr, left, right) {
  if (left === right) return arr[left];
  let mid = Math.floor((left + right) / 2);
  let left_max = maxSubArraySum(arr, left, mid);
  let right_max = maxSubArraySum(arr, mid + 1, right);
  let cross_max = maxCrossingSum(arr, left, mid, right);
  return Math.max(left_max, right_max, cross_max);
}

B

function maxCrossingSum(arr, left, mid, right) {
  let sum = 0
  let left_sum = -Infinity;
  for (let i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > left_sum) left_sum = sum;
  }
  sum = 0;
  let right_sum = -Infinity;
  for (let i = mid + 1; i <= right; i++) {
    sum += arr[i];
    if (sum > right_sum) right_sum = sum;
  }
  return left_sum + right_sum;
}

C

function maxCrossingSum(arr, left, mid, right) {
  let sum = 0;
  let left_sum = -Infinity;
  for (let i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > left_sum) left_sum = sum;
  }
  sum = 0;
  let right_sum = -Infinity;
  for (let i = mid + 1; i <= right; i++) {
    sum += arr[i];
    if (sum > right_sum) right_sum = sum;
  }
  return left_sum + right_sum;
}

D

}
;)xam_ssorc ,xam_thgir ,xam_tfel(xam.htaM nruter  
;)thgir ,dim ,tfel ,rra(muSgnissorCxam = xam_ssorc tel  
;)thgir ,1 + dim ,rra(muSyarrAbuSxam = xam_thgir tel  
;)dim ,tfel ,rra(muSyarrAbuSxam = xam_tfel tel  
;)2 / )thgir + tfel((roolf.htaM = dim tel  
;]tfel[rra nruter )thgir === tfel( fi  
{ )thgir ,tfel ,rra(muSyarrAbuSxam noitcnuf

💡 Hint

Look carefully for missing semicolons or syntax mistakes inside loops.

Option B is missing a semicolon after 'let sum = 0' which causes a syntax error in JavaScript.

🚀 Application

expert

Time Complexity of Maximum Subarray Divide and Conquer Algorithm

What is the time complexity of the divide and conquer algorithm for finding the maximum subarray sum in an array of size n?

A O(n^2)

B O(log n)

C O(n)

D O(n log n)

💡 Hint

Consider how the array is split and how the crossing sum is calculated at each level.

The algorithm splits the array into two halves recursively (log n levels) and computes crossing sums in linear time at each level, resulting in O(n log n) time complexity.

Practice

1. What is the main idea behind the Divide and Conquer approach to find the maximum subarray sum?

easy

A. Split the array into two halves, find max subarray in left, right, and crossing middle, then combine results

B. Sort the array and pick the largest element as the max subarray sum

C. Use a sliding window to find the max sum by expanding and shrinking the window

D. Calculate the sum of all elements and return it as the max subarray sum

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 subproblems

   Find max subarray in left half, right half, and crossing the middle, then take the maximum of these three.

3. Final Answer:

   Split array, find max left, right, and crossing sums, then combine -> Option A

4. Quick Check:

   Divide and conquer = split and combine max sums [OK]

Hint: Remember: divide array, conquer halves, combine max sums [OK]

Common Mistakes:

• Thinking sorting helps find max subarray sum
• Ignoring the crossing middle subarray
• Assuming max subarray is always the largest single element

2. Which of the following is the correct base case condition in a divide and conquer function to find the maximum subarray?

easy

A. If the array length is 1, return the single element

B. If the array length is 0, return 0

C. If the array length is 2, return the sum of both elements

D. If the array length is 1, return 0

Solution

1. Step 1: Identify base case for recursion

   When the array has only one element, that element itself is the max subarray sum.

2. Step 2: Return the single element value

   Return the element value directly as the max sum for that subarray.

3. Final Answer:

   Return the single element when array length is 1 -> Option A

4. Quick Check:

   Base case single element = element value [OK]

Hint: Base case: single element array returns that element [OK]

Common Mistakes:

• Returning 0 instead of the element for single element array
• Returning sum of two elements as base case
• Not defining a base case causing infinite recursion

3. What is the output of the following code snippet?

function maxCrossingSum(arr, left, mid, right) {
  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. 9

B. 7

C. 3

D. 5

Solution

1. Step 1: Calculate left sum from mid to left

   Starting at index 2 (value 3), sum = 3; then index 1 (-1), sum=2; index 0 (2), sum=4. Max leftSum = 4.

2. Step 2: Calculate right sum from mid+1 to right

   Starting at index 3 (-4), sum = -4; index 4 (5), sum=1. Max rightSum = 1.

3. Step 3: Add leftSum and rightSum

   4 + 1 = 5.

4. Final Answer:

   5 -> Option D

5. Quick Check:

   Left max 4 + Right max 1 = 5 [OK]

Hint: Sum left max from mid down, right max from mid+1 up, add [OK]

Common Mistakes:

• Adding wrong subarray sums crossing mid
• Mixing indices for left and right sums
• Using max element instead of max crossing sum

4. Identify the bug in this divide and conquer max subarray function:

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

medium

A. The base case should return 0 instead of arr[left]

B. The left recursive call should be maxSubArray(arr, left, mid)

C. The right recursive call should be maxSubArray(arr, mid, right)

D. The mid calculation is incorrect

Solution

1. Step 1: Check recursive calls range

   Left recursive call uses mid - 1, which excludes mid element incorrectly.

2. Step 2: Correct left recursive call to include mid

   Change left recursive call to maxSubArray(arr, left, mid) to include mid element.

3. Final Answer:

   Left recursive call should be maxSubArray(arr, left, mid) -> Option B

4. Quick Check:

   Include mid in left recursion [OK]

Hint: Include mid index in left recursion call [OK]

Common Mistakes:

• Excluding mid element in recursive calls
• Returning 0 instead of element in base case
• Incorrect mid calculation causing infinite recursion

5. Given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], what is the maximum subarray sum found using divide and conquer?

hard

A. 7

B. 5

C. 6

D. 4

Solution

1. Step 1: Identify the max subarray

   The subarray [4, -1, 2, 1] (indices 3-6) sums to 4 + (-1) + 2 + 1 = 6.

2. Step 2: Check extending right

   [4, -1, 2, 1, -5] = 1 < 6; [4, -1, 2, 1, -5, 4] = 5 < 6.

3. Step 3: Check extending left

   [-3, 4, -1, 2, 1] = 3 < 6; further left smaller.

4. Final Answer:

   6 -> Option C

5. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Check sums of all subarrays crossing mid carefully [OK]

Common Mistakes:

• Miscomputing as 7 by skipping the -3
• Choosing sum 5 by including the end
• Picking single largest element 4