This solution is linear and basically has an array called us (last sequence) and ms (max sequence). This array structure is as follows: [start sequence index, end sequence index, sum]. Then is computing the sum and saving the best partial sequence in ms. It returns an array with the above described structure. For instance, for input [-1, 5, 6, -…

max_sum.rb

# arreglo = [-1, 5, 6, -2, 20, -50, 4]
def max_sum (a)

  us = [0,0,a[0]]
  ms = Array.new(us)

  for i in 1..a.size-1 do
    new_sum = us[2] + a[i]
    if (new_sum < 0 or new_sum < a[i]) then
      us = [i,i,a[i]]
    else 
      us[2] = us[2] + a[i]
      us[1] = i
    end
    if (us[2] > ms[2]) then
      ms = Array.new(us)
    end
  end
  return ms
end