Level Order

 source code

Maximum subarray sum

Given an array of numbers, return the maximum sum of any continous subarray of numbers.

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

The subarray with the highest sum is [4, 5] with a sum of 9
Solution Time Space
Brute force O(n2) O(1)
Divide and conquer O(n log n) O(n)
Dynamic programming O(n) O(n)
Kadane's algorithm O(n) O(1)

Solution 1: Brute force

To find the maximum subarray sum:

  • Use two loops to iterate over all O(n2) possible subarrays
  • The outer loop decides where the subarray starts
  • The inner loop decides where the subarray ends
  • After each inner loop ends, you have the sum of the current subarray
  • This sum is the new max sum if it's higher than the current max sum

The max sum after checking all subarrays is the maximum subarray sum

def maximum_subarray_sum(numbers)
  n = numbers.length
  max_sum = 0
  (0 .. n-1).each do |i|
    sum = numbers[i]
    max_sum = [max_sum, sum].max
    (i+1 .. n-1).each do |j|
      sum += numbers[j]
      max_sum = [max_sum, sum].max
    end
  end
  max_sum
end
Time O(n2) Checking all O(n2) possible subarrays
Space O(1) The sum and max sum

Solution 2: Divide and conquer

The maximum subarray sum can exist in 1 of 3 places:

  • The left half of the array
  • The right half of the array
  • Crossing into both halves of the array

The divide and conquer approach recursively checks smaller subarrays and returns the highest sum found.

def maximum_subarray_sum(numbers)
  max_sum(numbers, 0, numbers.length-1)
end

def max_sum(numbers, low, high)
  return numbers[low] if low >= high
  mid = (low + high) / 2
  [
    max_sum(numbers, low, mid),
    max_sum(numbers, mid + 1, high),
    cross_sum(numbers, low, high),
  ].max
end

def cross_sum(numbers, low, high)
  mid = (low + high) / 2
  max_sum = sum = numbers[mid]
  (mid - 1).downto(low).each do |i|
    sum += numbers[i]
    max_sum = [max_sum, sum].max
  end
  sum = max_sum
  (mid + 1).upto(high).each do |i|
    sum += numbers[i]
    max_sum = [max_sum, sum].max
  end
  max_sum
end
Time O(n log n) Stack depth of O(log n) each checking O(n) values
Space O(log n) Max stack depth of O(log n)

Solution 3: Dynamic programming

Each value in the max_sums array is the maximum possible subarray sum in a subarray that includes numbers[i] 
def maximum_subarray_sum(numbers)
  n = numbers.length
  max_sums = Array.new(n)
  max_sums[0] = max_sum = numbers[0]
  (1 .. n-1).each do |i|
    max_sums[i] = numbers[i]
    if max_sums[i-1] > 0
      max_sums[i] += max_sums[i-1]
    end
    max_sum = [max_sum, max_sums[i]].max
  end
  max_sum
end
Time O(n) Loop through all values in the input array once
Space O(n) Space for an n-length array

Solution 4: Kadane's algorithm

This is effectively the dynamic programming approach above without needing space for an additional array. Since we only need to look at the previous value in the max sums array to determine the current value, we can use a single variable to track that value instead of an entire array. 
def maximum_subarray_sum(numbers)
  n = numbers.length
  max_sum = sum = numbers[0]
  (1 .. n-1).each do |i|
    if sum + numbers[i] > numbers[i]
      sum += numbers[i]
    else
      sum = numbers[i]
    end
    max_sum = [max_sum, sum].max
  end
  max_sum
end
Time O(n) Loop through all values in the input array once
Space O(1) The sum and max sum

Resources