23 lines
521 B
Ruby
23 lines
521 B
Ruby
# the trick is that at any point
|
|
# in the iteration if starting a new chain is
|
|
# better than your current score with this element
|
|
# added to it, then do so.
|
|
# the interesting part is proving the math behind it
|
|
def subarray_sum(arr)
|
|
curr = max = 0
|
|
first, last, curr_first = arr.size, 0, 0
|
|
arr.each_with_index do |e,i|
|
|
curr += e
|
|
if e > curr
|
|
curr = e
|
|
curr_first = i
|
|
end
|
|
if curr > max
|
|
max = curr
|
|
first = curr_first
|
|
last = i
|
|
end
|
|
end
|
|
return max, arr[first..last]
|
|
end
|