Interview Question: Find the Subarray with the Biggest Sum

I came across this interview question somewhere, and it stayed in my mind for some reason, so I solved it for fun. Here’s the problem:

Given an array of integers, find the sub-array with the greatest sum. For example, if the array is [0, 2, -4, 1], the greatest sum is 0 + 2 = 2. But if the array is [0, 2, -4, 9], the great sum is 0 + 2 - 4 + 9 = 7.

Sachin Shenoy’s solution

def solve(a):
    running_sum = 0
    max_sum = 0
    for v in a:
        running_sum += v
        if running_sum < 0:
            running_sum = 0
        max_sum = max(max_sum, running_sum)
    return max_sum


print(solve([3, -2, 1, 2]))

My solution

My solution is unnecessarily complex and recursive, when an iterative solution is preferable. But if you still want to read it, here it is:

Split the array into three parts:

1. Left, consisting of non-negative elements.

2. Middle, consisting of negative elements.

3. Right, starting with a non-negative element and going till the end of the array.

Now we need to decide whether to use only the left sub-array (which will have a non-negative sum), only the right (which will have a non-negative sum), or the entire array.

Here’s the code ¹:

def calc(array):
  i = 0
  left_sum = 0

  while array[i] >= 0:
    left_sum += array[i]
    ++i
    if i == array.length:
      return left_sum  # All elements are non-negative.

  # The middle sub-array begins here.
  middle_begin = i
  middle_sum = 0

  while array[i] < 0:
    middle_sum += array[i]
    if i == array.length:
      return left_sum

  right_begin = i
  right_sum = calc(array.suffix(i))

  return max(left_sum, right_sum, left_sum + right_sum + middle_sum)

This illustrates recursive thinking: don’t think of solving the entire problem. You’ll get stuck. Think of making one step of progress ².

This program is linear time. Why? Since it accesses each element exactly once. The max() call doesn’t contribute to time complexity since it performs two comparisons and two additions, not N.

In terms of space complexity, it’s linear, too. In fact, a more useful metric is additional space complexity, which is the amount of space the algorithm itself needs beyond the inputs and outputs. That’s constant time.

1. This code can throw an index out of bounds exception. To fix this, the while loops should be rewritten to check the index before checking the value at that index. For example, the first loop should be rewritten as

while True:
  if i == array.length:
    return left_sum
  if array[i] < 0:
    break
  left_sum += array[i]
  ++i

2. When writing a recursive algorithm, you need to guarantee progress, that the recursive call will operate on smaller data than the original call. Otherwise, you can get into infinite recursion.