Maximum Subarray Problem Solutions

The "Maximum Subarray" problem is a classic example in computer science, used to illustrate dynamic programming as well as divide and conquer strategies. It involves finding a contiguous subarray with the largest sum in a given array.

Dynamic Programming Solution

The dynamic programming approach, also known as Kadane's algorithm, iteratively computes the maximum subarray sum ending at each position.

function maxSubArray(nums: number[]): number {
  let maxSub = nums[0];
  let curSum = 0;

  for (let num of nums) {
    if (curSum < 0) {
      curSum = 0;
    }
    curSum += num;
    maxSub = Math.max(maxSub, curSum);
  }

  return maxSub;
}

Divide and Conquer Solution

The divide and conquer approach splits the array into two halves and recursively finds the maximum subarray sum in each half. It also considers the possibility of the maximum subarray crossing the midpoint.

function crossSum(nums: number[], left: number, right: number, mid: number): number {
  if (left === right) return nums[left];

  let leftSubsum = Number.NEGATIVE_INFINITY;
  let currSum = 0;
  for (let i = mid; i > left - 1; --i) {
    currSum += nums[i];
    leftSubsum = Math.max(leftSubsum, currSum);
  }

  let rightSubsum = Number.NEGATIVE_INFINITY;
  currSum = 0;
  for (let i = mid + 1; i < right + 1; ++i) {
    currSum += nums[i];
    rightSubsum = Math.max(rightSubsum, currSum);
  }

  return leftSubsum + rightSubsum;
}

function helper(nums: number[], left: number, right: number): number {
  if (left === right) return nums[left];

  const mid = Math.floor((left + right) / 2);

  const leftSum = helper(nums, left, mid);
  const rightSum = helper(nums, mid + 1, right);
  const crossSum = crossSum(nums, left, right, mid);

  return Math.max(Math.max(leftSum, rightSum), crossSum);
}

function maxSubArrayDivideAndConquer(nums: number[]): number {
  return helper(nums, 0, nums.length - 1);
}

Explanation

• Dynamic Programming: This approach iteratively updates a running sum and maximum sum, resetting the running sum if it becomes negative.
• Divide and Conquer: This method recursively solves the problem in subarrays and finds the maximum sum that crosses the middle of the array. Both methods offer a way to understand different algorithmic strategies and their applications in solving complex problems.