Cassidoo’s Interview question of the week | 445

[eayurt]

Hello

This week question is about moving numbers. Here it is.

Given an array of integers, find the contiguous subarray that has the largest sum and return that sum. A subarray must contain at least one element. If all elements are negative, return the largest (least negative) value. If you need a hint, look up Kadane’s Algorithm!

Example:

> maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4])
6
> maxSubarraySum([5])
5
> maxSubarraySum([-1, -2, -3, -4])
-1
> maxSubarraySum([5, 4, -1, 7, 8])
23

Happy coding!

[lpogic]

def maxSubarraySum a
  a.reduce [0, a[0]] do |acc, e|
    [n = [e + acc[0], e].max, [n, acc[1]].max]
  end.last
end

[JoshDev]

def max_subarray_sum(numbers)
  running_total = numbers.first

  numbers.reduce do |max_sum, number|
    running_total = [number, running_total + number].max
    [max_sum, running_total].max
  end
end

[Sean]

def max_subarray_sum(arr)
  (1..arr.size)
    .flat_map {
      arr.each_cons(it).map(&:sum)
    }.max
end

Probably horribly inefficient, but it works!

[fpsvogel]

I came up with something similar to @Sean‘s:

def max_subarray_sum(numbers)
  numbers.length.downto(1).map { |sublength|
    numbers.each_cons(sublength).map(&:sum).max
  }.max
end

After I read up on Kadane’s Algorithm:

def max_subarray_sum(numbers)
  running_total = max_sum = numbers.first

  numbers.drop(1).each do |n|
    running_total = [n, running_total + n].max
    max_sum = [max_sum, running_total].max
  end

  max_sum
end

An improvement from O(n^3) (I think) to O(n)! Still, a little sad that I lose the chaining

[eayurt]

very simple

def max_subarray_sum(array)
  max_sum = array.first
  current_sum = array.first

  array[1..].each do |element|
    current_sum = [element, current_sum + element].max
    max_sum = [max_sum, current_sum].max
  end

  max_sum
end

pp max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])

[izkreny]

Wow, I’m always positively surprised by the variety of provided solutions!

And here is mine slice’n’reduce verbose version, probably the slowest one (haven’t checked Kadane’s Algorithm yet)…
I will benchmark all the provided answers next week when the new interview QOTW arrives, just to be sure to include last-minute ones as well.

def max_subarray_sum_for(integers)
  return integers.first if integers.size == 1

  negative_integers_count = integers.count(&:negative?)

  case negative_integers_count
  when 0
    integers.sum
  when integers.size
    integers.max
  else
    max_sum = 0

    integers.size.times do |index|
      integers.slice(index..).reduce(0) do |sum, integer|
        max_sum = [max_sum, sum += integer].max
        sum
      end
    end

    max_sum
  end
end

[izkreny]

And here are the benchmarks, @fpsvogel and @eayurt are sharing gold medal for speed.

Array of 1_000 unique negative integers

eayurt ........................ each :   113804.1 i/s
fpsvogel ................. drop_each :   113086.7 i/s - same-ish: difference falls within error
josh_dev .................... reduce :    38288.6 i/s -     2.97x  slower
izkreny ......... times_slice_reduce :    35141.5 i/s -     3.24x  slower
lpogic ........ reduce_last_oneliner :    22463.3 i/s -     5.07x  slower
fpsvogel .... map_each_cons_oneliner :        3.8 i/s - 29904.19x  slower
sean ... flat_map_each_cons_oneliner :        3.6 i/s - 31400.30x  slower

Array of 1_000_000 unique negative integers

fpsvogel ................. drop_each :      113.4 i/s
eayurt ........................ each :      113.3 i/s - same-ish: difference falls within error
josh_dev .................... reduce :       37.3 i/s - 3.04x  slower
izkreny ......... times_slice_reduce :       35.6 i/s - 3.19x  slower
lpogic ........ reduce_last_oneliner :       22.0 i/s - 5.15x  slower
fpsvogel .... map_each_cons_oneliner :        ?!? i/s - too slow to calculate, sorry! 🐌
sean ... flat_map_each_cons_oneliner :        ?!? i/s - too slow to calculate, sorry! 🐢

Array of 1_000 unique positive integers

fpsvogel ................. drop_each :   112865.4 i/s
eayurt ........................ each :   112375.8 i/s - same-ish: difference falls within error
josh_dev .................... reduce :    37842.8 i/s -     2.98x  slower
izkreny ......... times_slice_reduce :    35318.0 i/s -     3.20x  slower
lpogic ........ reduce_last_oneliner :    22290.2 i/s -     5.06x  slower
fpsvogel .... map_each_cons_oneliner :        3.8 i/s - 30083.98x  slower
sean ... flat_map_each_cons_oneliner :        3.6 i/s - 31127.79x  slower

Array of 1_000_000 unique positive integers

fpsvogel ................. drop_each :      113.0 i/s
eayurt ........................ each :      112.5 i/s - same-ish: difference falls within error
josh_dev .................... reduce :       36.8 i/s - 3.07x  slower
izkreny ......... times_slice_reduce :       35.2 i/s - 3.21x  slower
lpogic ........ reduce_last_oneliner :       22.0 i/s - 5.13x  slower
fpsvogel .... map_each_cons_oneliner :        ?!? i/s - too slow to calculate, sorry! 🦥
sean ... flat_map_each_cons_oneliner :        ?!? i/s - too slow to calculate, sorry! 🐨

Array of 1_000 unique mixed integers

eayurt ........................ each :   106776.5 i/s
fpsvogel ................. drop_each :   106483.5 i/s - same-ish: difference falls within error
josh_dev .................... reduce :    36056.6 i/s -     2.96x  slower
lpogic ........ reduce_last_oneliner :    21745.2 i/s -     4.91x  slower
izkreny ......... times_slice_reduce :       79.9 i/s -  1336.56x  slower
fpsvogel .... map_each_cons_oneliner :        3.7 i/s - 28736.51x  slower
sean ... flat_map_each_cons_oneliner :        3.6 i/s - 29669.18x  slower

Array of 1_000_000 unique mixed integers

eayurt ........................ each :      113.0 i/s
fpsvogel ................. drop_each :      111.5 i/s - same-ish: difference falls within error
josh_dev .................... reduce :       37.2 i/s - 3.04x  slower
lpogic ........ reduce_last_oneliner :       21.7 i/s - 5.20x  slower
fpsvogel .... map_each_cons_oneliner :        ?!? i/s - too slow to calculate, sorry! 🐌
sean ... flat_map_each_cons_oneliner :        ?!? i/s - too slow to calculate, sorry! 🐢
izkreny ......... times_slice_reduce :        ?!? i/s - too slow to calculate, sorry! 🦥