Why Find Maximum Subarray Divide and Conquer in DSA Javascript?

The Big Idea

Discover how breaking a big problem into smaller pieces can save you hours of work!

The Scenario

Imagine you have a long list of daily profits and losses from your small business. You want to find the best continuous period where you made the most money. Doing this by checking every possible period manually would take forever!

The Problem

Manually checking every possible start and end day means looking at many combinations. This takes a lot of time and is easy to mess up. It's like trying to find the best part of a movie by watching every possible clip one by one.

The Solution

The divide and conquer method breaks the big problem into smaller parts, solves each part, and then combines the answers. This way, it quickly finds the best continuous period without checking every possibility.

Before vs After

✗ Before

function maxSubarraySum(arr) {
  let maxSum = -Infinity;
  for (let start = 0; start < arr.length; start++) {
    for (let end = start; end < arr.length; end++) {
      let sum = 0;
      for (let k = start; k <= end; k++) sum += arr[k];
      if (sum > maxSum) maxSum = sum;
    }
  }
  return maxSum;
}

✓ After

function maxSubarraySum(arr, left, right) {
  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);
}

What It Enables

This method lets you quickly find the most profitable continuous period in large data sets without wasting time on every possibility.

Real Life Example

A stock trader uses this to find the best time window to buy and sell stocks for maximum profit from historical price data.

Key Takeaways

Manual checking is slow and error-prone for large data.

Divide and conquer splits the problem to solve faster.

It finds the maximum subarray sum efficiently.

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