Get max subsum from an array

Question

I had this question on a test recently and don't understand at all what the question is asking for, especially based on the examples:

max_subsum

Write a method, max_subsum(numbers), which takes an array and returns the start and end indices of the consecutive range which has the largest sum.

max_subsum([100, -101, 200, -3, 1000]) == [2, 4]

max_subsum([1, 2, 3]) == [0, 2]

Hints: iterate through all the subarrays; compute the sum of each subarray and compare to the max subsum seen so far. A subarray is defined by its start index and end indices, so iterate through all pairs of indices. You should probably use two loops, one nested inside the other.

I don't see any subarrays in the examples. The output from the examples simply shows the indices of smallest and largest values in the array. If that's what the question is asking for, then what summation of subarrays is happening. I must be missing something simple, I just don't know what that is. Does someone else see it?

Answer 1

Here's my quick solution to your problem =)

Split the calls in order to understand what I'm doing =)

def max_subsum(a)
    (0...a.length).flat_map { |i| (i...a.length).map { |j| i..j } }.inject([a[0], 0..0]) { |max, i| a[i].inject(:+) > max.first ? [a[i].inject(:+),i ]: max }.last
end

Output:

max_subsum([100, -101, 200, -3, 1000])
=> 2..4
max_subsum([1, 2, 3])
=> 0..2

You can convert to array.. I did not bother as I like the range =)

A dynamic programming solution to this problem would be more efficient but I think you are expected to provide something along the lines of what I did during an exam :-)

Explanation:

(0...a.length).flat_map { |i| (i...a.length).map { |j| i..j } }

returns to me all the possible consecutive positions in the array. You can consider this your nested loops.

I'm then injecting the value [a[0], 0..0] and assuming it's the solution: a[0] being the max value and 0..0 being the start to end index. Inside inject, I'm comparing the max to the sum of the current slice of the array from flat_map, if it's bigger, I return the slice and the max.

Answer 2

The Kadane's Algorithm is what you want. In this blog you could find good references too.

Answer 3

These are the first array's subarrays along with their sums:

[100].inject(:+)                       #=>   100
[100, -101].inject(:+)                 #=>    -1
[100, -101, 200].inject(:+)            #=>   199
[100, -101, 200, -3].inject(:+)        #=>   196
[100, -101, 200, -3, 1000].inject(:+)  #=>  1196
     [-101].inject(:+)                 #=>  -101
     [-101, 200].inject(:+)            #=>    99
     [-101, 200, -3].inject(:+)        #=>    96
     [-101, 200, -3, 1000].inject(:+)  #=>  1096
           [200, -3, 1000].inject(:+)  #=>  1197
                [-3, 1000].inject(:+)  #=>   997
                    [1000].inject(:+)  #=>  1000

[200, -3, 1000] has the largest sum