In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with su…

Maximum continuous subarray

#max sub array sum return sum and sub array kadane's algorithm

def max_subarray(collection)
  temp_sum = 0
  max_sum = 0
  check_sum = 0
  begin_point = 0
  end_point = collection.length - 1
  max_subarray = []
  collection.each_with_index do |element, index|
    temp_sum += element
    
    if temp_sum < 0
      temp_sum = 0 
      begin_point = index + 1   
    end

    if temp_sum > max_sum
      max_sum = temp_sum
      end_point = index
    end
  end
  max_subarray = collection.slice(begin_point .. end_point)
  p "maximum continous sum is #{max_sum} in subarray: #{max_subarray}"
end