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

Practice - 5 Tasks

1fill in blank

easy

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

DSA Typescript

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 Typescript

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

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

AmidSum

BcrossSum

CtotalSum

DmaxSum

Attempts:

3 left

💡 Hint

Common Mistakes

Using a variable not representing crossing sum.

Forgetting to include crossing sum in max calculation.

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 left crossing sum.

DSA Typescript

for (let i = mid; i >= [1]; i--) { leftSum += arr[i]; maxLeft = Math.max(maxLeft, leftSum); }

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

Aleft

B0

Cmid

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of left index.

Using mid or right incorrectly as loop boundary.

The loop must go down to the left boundary index.

4fill in blank

hard

Fill both blanks to calculate right crossing sum correctly.

DSA Typescript

let rightSum = 0; let maxRight = -Infinity; for (let j = mid + 1; j [1] [2]; j++) { rightSum += arr[j]; maxRight = Math.max(maxRight, rightSum); }

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

A<=

B<

Cright

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using < instead of <= causing missing last element.

Using left instead of right as boundary.

The loop runs from mid+1 up to right index (inclusive).

5fill in blank

hard

Fill all three blanks to complete the recursive maximum subarray function.

DSA Typescript

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

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

Aarr[left]

Bmid

Cmid + 1

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Returning arr[right] in base case.

Using wrong indices in recursive calls.

Base case returns single element; recursive calls split at mid and mid+1.

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