answer.rb

def max_sum_of_interval(list)
  current_total = 0
  max_total = 0

  list.each do |item, index|
    if item + current_total >= 0
      current_total += item
      max_total = current_total if current_total > max_total
    else
      current_total = 0
    end
  end

  max_total
end

# Outputs a range representing a set of start and stop indices 
# of the input list that generates the maximum sum.
# There may be multiple sets of start and stop indices, this
# method only generates the one nearest the end of the list.
def max_sum_of_interval_with_indices(list)
  current_total = 0
  max_total = 0

  start_index = 0
  stop_index = 0

  list.each_with_index do |item, index|
    if item + current_total >= 0
      current_total += item
      max_total = current_total if current_total > max_total
      stop_index = index if item + current_total >= current_total
    else
      current_total = 0
      start_index = index + 1
      stop_index = index + 1
    end
  end

  [start_index, stop_index]
end

spec.rb

require_relative 'answer'

describe 'the answer' do
  it 'should output the maximum value' do
    list = [-2, 11, -4, 13, -5, -2]
    max_sum_of_interval(list).should == 20
    max_sum_of_interval_with_indices(list).should == [1, 3]

    list = [3, -1, -1, 9]
    max_sum_of_interval(list).should == 10
    max_sum_of_interval_with_indices(list).should == [0, 3]

    list = [-2, -5, -4, 13, -5, -2]
    max_sum_of_interval(list).should == 13
    max_sum_of_interval_with_indices(list).should == [3, 3]

    list = [1, 1, -1, 1, 1]
    max_sum_of_interval(list).should == 3
    max_sum_of_interval_with_indices(list).should == [0, 4]

    list = [1, 1, -1, 1, 1, 0, 0, 1]
    max_sum_of_interval(list).should == 4
    max_sum_of_interval_with_indices(list).should == [0, 7]

    list = [1, 1, -5, 1, 1]
    max_sum_of_interval(list).should == 2
    max_sum_of_interval_with_indices(list).should == [3, 4]

    list = [-1, 1, 1, -5, 1, 1]
    max_sum_of_interval(list).should == 2
    max_sum_of_interval_with_indices(list).should == [4, 5]

    list = [-1, 2, -1, 2, -1]
    max_sum_of_interval(list).should == 3
    max_sum_of_interval_with_indices(list).should == [1, 3]

    list = [5, -1, -1, -1, -1, 6]
    max_sum_of_interval(list).should == 7
    max_sum_of_interval_with_indices(list).should == [0, 5]

    list = [5, -1, -1, -1, -1, -1, 6]
    max_sum_of_interval(list).should == 6
    max_sum_of_interval_with_indices(list).should == [0, 6]

    list = [5, -1, -1, -1, -1, -1, -1, 6]
    max_sum_of_interval(list).should == 6
    max_sum_of_interval_with_indices(list).should == [7, 7]
  end
end