Find Maximum Subarray Divide and Conquer in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle index of the array segment.

DSA Javascript

const mid = Math.floor((left + [1]) / 2);

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cmid

Darr.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using left twice instead of left and right.

Using array length instead of right index.

The middle index is calculated by averaging left and right indices.

2fill in blank

medium

Complete the code to return the maximum of three values.

DSA Javascript

return Math.max(leftSum, rightSum, [1]);

Drag options to blanks, or click blank then click option'

AcrossSum

BmidSum

CtotalSum

DmaxSum

Attempts:

3 left

💡 Hint

Common Mistakes

Using midSum which is undefined.

Using totalSum which is not calculated.

The maximum subarray sum is the max of left, right, and crossing sums.

3fill in blank

hard

Fix the error in the loop that calculates the left crossing sum.

DSA Javascript

for (let i = mid; i >= [1]; i--) {

Drag options to blanks, or click blank then click option'

A0

Bright

Cleft

Dmid

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of left index causes wrong range.

Using right index causes loop to never run.

The loop should go from mid down to left boundary.

4fill in blank

hard

Fill both blanks to calculate the right crossing sum correctly.

DSA Javascript

for (let j = mid + 1; j <= [1]; j++) {
  sum += arr[j];
  rightSum = Math.max(rightSum, [2]);
}

Drag options to blanks, or click blank then click option'

Aright

Bsum

Carr[j]

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using left instead of right for loop end.

Updating rightSum with arr[j] instead of sum.

The loop runs to right boundary and updates rightSum with current sum.

5fill in blank

hard

Fill all three blanks to complete the divide and conquer function.

DSA Javascript

function maxSubArray(arr, [1], [2]) {
  if ([1] === [2]) return arr[[1]];
  const mid = Math.floor(([1] + [2]) / 2);
  const leftSum = maxSubArray(arr, [1], mid);
  const rightSum = maxSubArray(arr, mid + 1, [2]);
  const crossSum = maxCrossingSum(arr, [1], mid, [2]);
  return Math.max(leftSum, rightSum, crossSum);
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up left and right parameters.

Using mid instead of left or right in base case.

The function uses left and right indices to divide the array and find max sums.

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