Find the Subarray with the Maximum Sum

Instructions

Write a function that returns the subarray with the highest sum from a given array of numbers. The function should use Kadane's Algorithm to find the maximum sum subarray efficiently.

Examples

Here are a few examples to illustrate how the maxSubArray function works:

Example 1

Input: [1, -2, 3, 4, -1, 2, 1, -5, 4] Output: [3, 4, -1, 2, 1] (10)

Example 2

Input: [-2, -3, 4, -1, -2, 1, 5, -3] Output: [4, -1, -2, 1, 5] (7)

Example 3

Input: [5, 4, -1, 7, 8] Output: [5, 4, -1, 7, 8] (19)

The example solution provided demonstrates a function called maxSubArray that returns the subarray with the highest sum. The function uses Kadane's Algorithm to calculate the maximum sum subarray iteratively, keeping track of the current sum and the maximum sum found so far.

Find Maximum Subarray

  const maxSubArray = (nums) => {
    if (nums.length === 0) return [];

    let maxSum = nums[0];
    let currentSum = nums[0];
    let start = 0, end = 0, tempStart = 0;

    for (let i = 1; i < nums.length; i++) {
      if (currentSum < 0) {
        currentSum = nums[i];
        tempStart = i;
      } else {
        currentSum += nums[i];
      }

      if (currentSum > maxSum) {
        maxSum = currentSum;
        start = tempStart;
        end = i;
      }
    }

    return nums.slice(start, end + 1);
  }