Ruby Program to find contiguous subarray within a one dimensional array of numbers (containing at least one positive number) which has the largest sum

contiguous_subarray.rb

# Question:
# Write a RoR program to find the contiguous subarray within a onedimensional
# 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 sum 6.
# The program should run as follows <bold is user entry>:
# Enter the array : 
# -2 1 -3 4 -1 2 1 -5 4
# => [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Largest SubArray
# Start Index: 3
# Length: 4
# Sum: 6
# Elements: 4 -1 2 1


def contiguous_subarray(array)
  largest = {
    :sum   => array[0],
    :start => 0,
    :end   => 0
  }
  (0 .. array.length-1).each do |start_at|
    sum = 0
    start_num = array[start_at]
    next if largest[:sum] > start_num and start_num < 0

    (start_at .. array.length-1).each do |end_at|
      end_num = array[end_at]
      sum += end_num

      if sum > largest[:sum]
        largest[:sum]   = sum
        largest[:start] = start_at
        largest[:end]   = end_at
      end
    end
  end

  puts "Largest SubArray"
  puts "Start Index: #{largest[:start]}"
  puts "Length: #{array[largest[:start] .. largest[:end]].length}"
  puts "Sum: #{largest[:sum]}"
  puts "Elements: #{array[largest[:start] .. largest[:end]].join(' ')}"
end

puts "Enter the array :"
input_array = gets.split.map(&:to_i)
contiguous_subarray(input_array)

This is the brute force approach which results in TLE (time limit exceeded) on large set of array.
You can test it out on this leetcode question.

A better optimized approach would be to use Kadane's Algorithm