15 lines
485 B
Crystal
15 lines
485 B
Crystal
# 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
|
|
e > curr && (curr = e; curr_first = i)
|
|
curr > max && (max = curr; first = curr_first; last = i)
|
|
end
|
|
return max, arr[first..last]
|
|
end
|