Contiguous sum subarray decomposed

Let's look at the problem that you might've seen before:

Given an array of integers, find the contiguous subarray which has the largest sum and return it.

maxSubArray([-2, 1, 4, -1, 4]) //  8

Imagine if you would've asked this problem in an interview. Give yourself a few minutes to think of a couple of vector to attack this problem. What if you would've been asked to come up with as much approaches as possible? If you never seen this problem before, chances are that it might stumble you for some time, while you're coming up with the reasonable solution.

Firstly, the question is intentionally left a little vague. One important detail is whether we should consider empty subarray [].

Let's start with something slow and current. We could calculate a sum for every possible subarray. How about this:

/*
    O(n^3)
*/
let maxSubArrayBruteN3 = (arr) => {
  if (!arr.length) { return null }

  let max = arr[0]

  for (let i = 0; i < arr.length; i++) {
    for (let j = i; j < arr.length; j++) {
      let sum = 0

      for (let k = i; k <= j; k++) {
        sum += arr[k]
      }

      max = Math.max(sum, max)
    }
  }

  return max
}

The time complexity is `O(n^3)`.

This code is too rough, notice how we can calculate the sum at the same time while iterating over the inner loop:

/*
    O(n^2)
*/
let maxSubArrayBruteN2 = (arr) => {
  if (!arr.length) { return null }

  let max = -Infinity

  for (let i = 0; i < arr.length; i++) {
    let curr = 0

    for (let j = i; j < arr.length; j++) {
      curr += arr[j]
      max = Math.max(max, curr)
    }
  }

  return max
}

This gives us `O(n^2)`.

In order to improve it further we need to make an important observation. Our subset can span over the multiple contiguous elements: how can we set the right borders?

Let's try to work through a few examples first:

maxSubArray([1, 2, 3, -10, 5]) //  5
maxSubarray([1, 2, 3, -1, 5]) // 10 = 1 + 2 + 3 - 1 + 5

There's certainly a situation where you want to disregard anything that was behind and start all over again. It might want to give you an idea that it's worth to keep track of the current sum of elements, while you're traversing the array linearly.

Actually, there's a Kadane's algorithm that says:

`MaxSum(i) = max(A[i], MaxSum(i - 1) + A[i])`

It means that at any given index, the maximum subarray sum is either the MaxSum of preceding elements including current, or just the current element itself. Intuitively, it makes sense. If your current sum so far is so low, that even the current element itself is bigger, you just want to left behind everything that was before and start a new subset starting from the current index.

/*
    Bottom-up DP also known as Kadane's algorithm
*/
let maxSubArrayDp = (arr) => {
  if (!arr.length) { return null }

  let max = arr[0] // let max = 0, if empty subsets matter
  let maxEndingHere = arr[0]

  for (let i = 1; i < arr.length; i++) {
    maxEndingHere = Math.max(arr[i], arr[i] + maxEndingHere)
    max = Math.max(max, maxEndingHere)
  }

  return max
}

If we are allowed to modify our input array, this approach might be a bit more expressive:

/*
    Modifies array
*/
let maxSubArrayDp_RW = (arr) => {
  if (!arr.length) { return null }

  let max = arr[0]

  for (let i = 1; i < arr.length; i++) {
    arr[i] = Math.max(arr[i], arr[i] + arr[i - 1])
    max = Math.max(max, arr[i])
  }

  return max
}

Some may wonder, how is this a dynamic programming approach if all we do is traversing the array linearly. The answer is in Kadane's recurrence above. The most obvious form of Kadane's algorithm is a bottom-up form of dynamic programming problem.

We can construct a recursive version of it:

/*
    Recursive version
*/
let maxSubArrayDp_Rec = (arr) => {
  if (!arr.length) { return null }

  let _maxSubArray = (arr, n) => {
    if (n === 0) { return arr[0] }

    return Math.max(
      arr[n],
      _maxSubArray(arr, n - 1) + arr[n]
    )
  }

  let max = _maxSubArray(arr, arr.length - 1)

  return max
}

Note that we can use memoization here as well, though we will not benefit from it as we compute result for every index only once.

What if interviewer asks you to return the range of your item as well? In that case you'll need to agree on two questions:

If you careful about when you're changing the border of your subarray, it's pretty straightforward. Comparison signs are important, make sure you put them properly.

/*
    Returns range
*/
let maxSubArrayDp_LR = (arr) => {
  if (!arr.length) { return null }

  let max = arr[0]
  let maxEndingHere = arr[0]

  let [ l, r, window ] = [ 0, 0, 0 ]

  for (let i = 1; i < arr.length; i++) {
    /*
      >= vs >
      > - makes the sequence longer
      i.e. [-1, +1, 2]
    */
    if (arr[i] >= maxEndingHere + arr[i]) {
      maxEndingHere = arr[i]
      window = 0
    } else {
      maxEndingHere = arr[i] + maxEndingHere
      window++
    }

    /*
      > vs >=
      >= would rewrite if same sum appear later
      i.e. [+1, +2, -3, +1, +2]
    */
    if (maxEndingHere >= max) {
      max = maxEndingHere
      r = i
      l = i - window
    }
  }

  console.log('LR:', l, r)
  return max
}

You might've been asked to solve it using 'divide and conquer' approach which is slightly more subtle.

/*
    Divide and Conquer: O(N * log(N))
*/
let maxSubArrayDC = (arr) => {
  let _maxCrossingSum = (arr, low, mid, high) => {
    let leftSum = 0
    let leftMax = -Infinity

    for (let i = mid; i >= low; i--) {
      leftSum += arr[i]
      leftMax = Math.max(leftSum, leftMax)
    }

    let rightSum = 0
    let rightMax = -Infinity

    for (let i = mid + 1; i <= high; i++) {
      rightSum += arr[i]
      rightMax = Math.max(rightSum, rightMax)
    }

    return leftMax + rightMax
  }

  let _maxSubArraySum = (arr, low, high) => {
    if (low == high) {
      return arr[low]
    }

    let mid = Math.floor((low + high) / 2)

    /*
      Return maximum out of following:
      - Maximum subarray sum in left half
      - Maximum subarray sum in right half
      - Maximum subarray sum such that the
          subarray crosses the midpoint
    */
    return Math.max(
      _maxSubArraySum(arr, low, mid),
      _maxSubArraySum(arr, mid + 1, high),
      _maxCrossingSum(arr, low, mid, high)
    );
  }

  return _maxSubArraySum(arr, 0, arr.length - 1)
}

I think this is a awesome toy problem that works really well as a showcase of what the more advanced programming concepts look like.

I hope that if you're learning, it'll help to show you how the problem could be attacked from the different angles and if you're seasoned developer, you can just skim through to make sure we're both didn't miss anything. Have a nice streak!