Find Maximum Subarray Divide and Conquer in DSA Javascript - Build from Scratch

Find Maximum Subarray using Divide and Conquer

📖 Scenario: You are analyzing daily temperature changes to find the longest period of increasing temperature. This helps in understanding heat waves.

🎯 Goal: Build a program that finds the maximum sum of a contiguous subarray using the divide and conquer method.

📋 What You'll Learn

Create an array called nums with the exact values [2, -1, 3, -4, 5, -2, 1, -3, 4].

Create a helper function called maxCrossingSum that finds the maximum sum crossing the middle of the array.

Create a recursive function called maxSubArraySum that uses divide and conquer to find the maximum subarray sum.

Print the maximum subarray sum found by maxSubArraySum.

💡 Why This Matters

🌍 Real World

Finding maximum subarrays helps in analyzing trends like temperature changes, stock prices, or sales data to detect periods of growth or decline.

💼 Career

Understanding divide and conquer algorithms and maximum subarray problems is important for software engineers working on data analysis, financial software, and performance optimization.

1

Create the array of numbers

Create an array called nums with these exact values: [2, -1, 3, -4, 5, -2, 1, -3, 4].

DSA Javascript

# Create the array nums with the given values
// Your code here

Hint

Use const nums = [...] to create the array with the exact numbers.

2

Create the maxCrossingSum helper function

Create a function called maxCrossingSum that takes arr, left, mid, and right as parameters and returns the maximum sum of a subarray crossing the middle index.

DSA Javascript

const nums = [2, -1, 3, -4, 5, -2, 1, -3, 4];

// Create maxCrossingSum function below
// Your code here

Hint

Use two loops: one from middle to left, one from middle+1 to right, to find max sums on both sides.

3

Create the maxSubArraySum recursive function

Create a recursive function called maxSubArraySum that takes arr, left, and right as parameters and returns the maximum subarray sum using divide and conquer. Use maxCrossingSum inside it.

DSA Javascript

const nums = [2, -1, 3, -4, 5, -2, 1, -3, 4];

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_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}

// Create maxSubArraySum function below
// Your code here

Hint

Divide the array into two halves, find max subarray in left, right, and crossing middle, then return the max.

4

Print the maximum subarray sum

Print the result of calling maxSubArraySum with nums, 0, and nums.length - 1.

DSA Javascript

const nums = [2, -1, 3, -4, 5, -2, 1, -3, 4];

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_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}

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

// Print the maximum subarray sum below
// Your code here

Hint

Call maxSubArraySum(nums, 0, nums.length - 1) and print the result.

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