maxSubArray

maxSubArray.js

// Cubic O(n³)
// https://www.youtube.com/watch?v=2MmGzdiKR9Y Feb: 01/2019
function maxSubArray(nums) {
  let maximumSubArraySum = Number.NEGATIVE_INFINITY;

  /*
      We will use these outer 2 for loops to investigate all
      windows of the array.
      
      We plant at each 'left' value and explore every
      'right' value from that 'left' planting.
      These are our bounds for the window we will investigate.
    */
  for (let left = 0; left < nums.length; left++) {
    for (let right = left; right < nums.length; right++) {
      // Let's investigate this window
      let windowSum = 0;

      // Add all items in the window
      for (let k = left; k <= right; k++) {
        windowSum += nums[k];
      }

      // Did we beat the best sum seen so far?
      maximumSubArraySum = Math.max(maximumSubArraySum, windowSum);
    }
  }

  return maximumSubArraySum;
}

// Quadratic Time O(n²)
function maxSubArray(nums) {
  let n = nums.length;
  let maximumSubArraySum = Number.NEGATIVE_INFINITY;

  for (let left = 0; left < n; left++) {
    /*
        Reset our running window sum once we choose a new
        left bound to plant at. We then keep a new running
        window sum.
      */
    let runningWindowSum = 0;

    /*
        We improve by noticing we are performing duplicate
        work. When we know the sum of the subarray from
        0 to right - 1...why would we recompute the sum
        for the subarray from 0 to right?
        This is unnecessary. We just add on the item at
        nums[right].
      */
    for (let right = left; right < n; right++) {
      // We factor in the item at the right bound
      runningWindowSum += nums[right];

      // Does this window beat the best sum we have seen so far?
      maximumSubArraySum = Math.max(maximumSubArraySum, runningWindowSum);
    }
  }

  return maximumSubArraySum;
}


// Linear Time O(n)
export function maxSubArray(nums) {
  /*
      We default to say the the best maximum seen so far is the first
      element.

      We also default to say the the best max ending at the first element
      is...the first element.
    */
  let maxSoFar = nums[0];
  let maxEndingHere = nums[0];

  /*
      We will investigate the rest of the items in the array from index
      1 onward.
    */
  for (let i = 1; i < nums.length; i++) {
    /*
        We are inspecting the item at index i.

        We want to answer the question:
        "What is the Max Contiguous Subarray Sum we can achieve ending at index i?"

        We have 2 choices:

        maxEndingHere + nums[i] (extend the previous subarray best whatever it was)
          1.) Let the item we are sitting at contribute to this best max we achieved
          ending at index i - 1.

        nums[i] (start and end at this index)
          2.) Just take the item we are sitting at's value.

        The max of these 2 choices will be the best answer to the Max Contiguous
        Subarray Sum we can achieve for subarrays ending at index i.

        Example:
        index     0  1   2  3   4  5  6   7  8
        Input: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
                 -2, 1, -2, 4,  3, 5, 6,  1, 5    'maxEndingHere' at each point
        
        The best subarrays we would take if we took them:
          ending at index 0: [ -2 ]           (snippet from index 0 to index 0)
          ending at index 1: [ 1 ]            (snippet from index 1 to index 1) [we just took the item at index 1]
          ending at index 2: [ 1, -3 ]        (snippet from index 1 to index 2)
          ending at index 3: [ 4 ]            (snippet from index 3 to index 3) [we just took the item at index 3]
          ending at index 4: [ 4, -1 ]        (snippet from index 3 to index 4)
          ending at index 5: [ 4, -1, 2 ]     (snippet from index 3 to index 5)
          ending at index 6: [ 4, -1, 2, 1 ]  (snippet from index 3 to index 6)
          ending at index 7: [ 4, -1, 2, 1, -5 ]    (snippet from index 3 to index 7)
          ending at index 8: [ 4, -1, 2, 1, -5, 4 ] (snippet from index 3 to index 8)

        Notice how we are changing the end bound by 1 everytime.
      */
    maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);

    // Did we beat the 'maxSoFar' with the 'maxEndingHere'?
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }

  return maxSoFar;
}

// Linear time variation O(n)
// https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
function maxSubArraySum2(a) {
  let size = a.length;
  let max_so_far = Number.NEGATIVE_INFINITY;
  let max_ending_here = max_so_far;

  for (let i = 0; i < size; i++) {
    max_ending_here = max_ending_here + a[i];
    if (max_so_far < max_ending_here) max_so_far = max_ending_here;
    if (max_ending_here < 0) max_ending_here = 0;
  }
  return max_so_far;
}