Max Subarray second version

max_subarray_2.rb

def find_max_subarray(array)
  #initialize all variables to zero
  max_sum = current_sum = current_start = start_idx = end_idx = cursor = 0

  # Go through individual element
  for cursor in 0...array.length
    # current_sum is the previous sum plus current element
    current_sum += array[cursor]
    if current_sum > max_sum # the case where the current sum is greater than the best sum so far.
      # we set best sum so far to current sum
      # update the start_idx to the starting point of current starting point
      # and set the end_idx to the current point
      max_sum = current_sum
      start_idx = current_start
      end_idx = cursor 
    elsif current_sum < 0
      #if the current sum is less than zero. it's better off we just start over as a new sub-array
      #in this case, set current sum to zero and start the current subarray from next element
      current_sum = 0 
      current_start = cursor + 1
    end
  end

  array.slice(start_idx, end_idx - start_idx+1)
end

a = [
  [3,5,1,-9,4],
  [-1,-2,-1,1,-5,-1],
  [5, 21, -30, 6, 9, 15, 20, -80],
  [-1, 2, 5, -1, 3, -2, 1]
]

a.each do |x|
  p find_max_subarray(x)
end

#Outputs from above code are
# [3, 5, 1]
# [1]
# [6, 9, 15, 20]
# [2, 5, -1, 3]

# Testcase
# describe #find_max_subarray do
#   it "should return the max slice" do
#     input = [-1, 2, 5, -1, 3, -2, 1]
#     find_max_subarray(input).should == [2, 5, -1, 3]
#   end
# end