The Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]

Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

Solution

Given

You are given an array of numbers.

Return

Return a single number. This number represents the sum of a subarray of the given array. Specifically, it represents the sum of all of the values in the subarray that has the greatest sum. A subarray is a set of consecutive values in an array. The smallest possible subarray is any single value in the array. The largest possible subarray is the entire array.

Approach One (Brute Force)

The first thought that may come to mind is to simply check the sum of every single subarray in the array. Then, you will be guaranteed to find the maximum subarray at some point. This can be done with a loop nested within a loop. The outer loop will iterate through the array. It will identify a starting index for the inner loop with the variable 'i'. The sum of the current subarray will be tracked throughout an iteration of the outer array. At each new iteration, the current subarray sum will be reset back to just the value at the new current index. The inner loop will iterate through the rest of array starting at the current starting index(i). At each iteration, it will add its current value to the current subarray sum and compare it to the max. If it is greater than the max, it will replace the max. This method will find the correct answer. However, it runs in O(N^2) due to the its loop nested within a loop. The length of both loops depend on the length of the input array. The space complexity is constant. The only space being used is the variable storing the max subarray sum. The amount of space being used does not depend on the length of the input array.

function maxSubarray(array) {
  let max = array[0] // the running max that will be returned at the end
  let current // sum of current subarray
  for (let i = 0; i < array.length; i++) { 
    for (let j = i; j < array.length; j++) {
      if (j === i) { // if we are at the beginnig of an iteration of the outer loop, set the current sum to just he current value
        current = array[i]
      } else { // as we loop through, add the current value to the sum
        current += array[j]
      }
      max = Math.max(current, max) // check if the current value is greater than the max and replace it if so
    }
  }
  return max
}

Approach Two (Dynamic Programming/Kadane's Algorithm)

This problem can be solved in O(N) time. In other words, it can be done using a single loop. The method to use is a dynamic programming method called Kadane's Algorithm. This algorithm uses the information found at each index to do a little more than just add to the current sum and check if it is the max. It also uses that information to essentially check if it is moving the current sum in the right direction or if it should scrap the current sum and start a new one. As you iterate through the array, don't just think about the current sum every step of the way, imagine the subarray itself that is responsible for creating the sum. Would adding the current value to the current subarray create the highest potential sum? Or would scrapping the current subarray and just keeping the current value provide a greater subarray? Kadane's algorithms uses a way to check for this at every iteration. It also still checks if the max should be replaced at each iteration, similar to the brute force method. This method runs in O(N) time because of the single loop and O(1) space because the only space being used is to track the current and the max.

function maxSubarray(array) {
  let max = array[0]
  let current = array[0]
  for (let i = 1; i < array.length; i++) {
    current = Math.max(array[i], current + array[i])
    max = Math.max(max, current)
  }
  return max
}