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

Find Maximum Subarray using Divide and Conquer

📖 Scenario: Imagine you are analyzing daily temperature changes over a week. You want to find the longest period where the temperature rise was the highest overall. This is like finding the maximum sum of a continuous subarray in a list of numbers.

🎯 Goal: You will build a program that uses the divide and conquer method to find the maximum sum of a continuous subarray in a given array of numbers.

📋 What You'll Learn

Create an array called nums with the exact values [2, -4, 3, -1, 5, -6, 1, 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 subarray sums helps in financial analysis to find the best time to buy and sell stocks for maximum profit.

💼 Career

Understanding divide and conquer algorithms is essential for software engineers working on performance-critical applications and algorithm design.

1

Create the array of numbers

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

DSA Typescript

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

Hint

Use const nums: number[] = [2, -4, 3, -1, 5, -6, 1, 4]; to create the array.

2

Create the maxCrossingSum helper function

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

DSA Typescript

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

// Create maxCrossingSum function below
// Your code here

Hint

Use two loops: one going left from mid, one going right from mid+1, to find max sums, then add them.

3

Create the maxSubArraySum recursive function

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

DSA Typescript

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

function maxCrossingSum(arr: number[], left: number, mid: number, right: number): number {
    let sum = 0;
    let leftSum = Number.NEGATIVE_INFINITY;
    for (let i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > leftSum) leftSum = sum;
    }
    sum = 0;
    let rightSum = Number.NEGATIVE_INFINITY;
    for (let i = mid + 1; i  rightSum) rightSum = sum;
    }
    return leftSum + rightSum;
}

// Create maxSubArraySum function below
// Your code here

Hint

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

4

Print the maximum subarray sum

Use console.log to print the result of calling maxSubArraySum with nums, 0, and nums.length - 1 as arguments.

DSA Typescript

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

function maxCrossingSum(arr: number[], left: number, mid: number, right: number): number {
    let sum = 0;
    let leftSum = Number.NEGATIVE_INFINITY;
    for (let i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > leftSum) leftSum = sum;
    }
    sum = 0;
    let rightSum = Number.NEGATIVE_INFINITY;
    for (let i = mid + 1; i  rightSum) rightSum = sum;
    }
    return leftSum + rightSum;
}

function maxSubArraySum(arr: number[], left: number, right: number): number {
    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);
}

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

Hint

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