Max Consecutive Sum The problem: Find the maximum sum possible from picking a contiguous subsequence of an array. [-1, 5, 6, -2, 20, -50, 4] What is the largest sum of contiguous elements available in this list? In the example above, the maximum sum would be 29: [-1, 5, 6, -2, 20, -50, 4], because (5 + 6 - 2 + 20 = 29). End one element later and…

max_consecutive_sum_calculator.rb

class MaxConsecutiveSumCalculator

  attr_reader :result

  def initialize(numbers, debug_steps = false)
    raise "Input array shouldn't be nil or empty" if numbers.nil? || numbers.empty?


    @original_numbers= numbers.clone

    @cursor = calculate_sum(numbers.clone, debug_steps)

    @result ={}
    @result[:sum] = @cursor.delete(:sum)
    @result[:cursor] = @cursor
    @result[:subarray] = @original_numbers.clone[@cursor[:left]..@cursor[:right]]
  end

  private

  def calculate_sum(numbers, debug_steps)
    boundaries= {}
    boundaries[:left] =0
    boundaries[:right] = numbers.length - 1

    cursor = boundaries.clone

    while boundaries[:left] != boundaries[:right]
      # decide if we process left or right element 
      if numbers[boundaries[:left]] <= numbers[boundaries[:right]]
        # process first array element
        if numbers[boundaries[:left]] > 0
          numbers[boundaries[:left]+1] += numbers[boundaries[:left]]
        else
          cursor[:left] = boundaries[:left] + 1
        end
        numbers[boundaries[:left]] = 0
        boundaries[:left] = boundaries[:left] + 1

      else
        # process last array element
        if numbers[boundaries[:right]] > 0
          numbers[boundaries[:right] - 1] +=numbers[boundaries[:right]]
        else
          cursor[:right] = boundaries[:right] - 1
        end
        numbers[boundaries[:right]] = 0
        boundaries[:right] = boundaries[:right] -1

      end

      puts numbers.inspect if debug_steps
    end

    cursor[:sum] = numbers[boundaries[:left]]

    cursor
  end

end

max_consecutive_sum_calculator_spec.rb

require 'rspec'
require_relative './max_consecutive_sum_calculator'
require_relative './recursive_max_consecutive_sum_calculator'

describe MaxConsecutiveSumCalculator do
  [
      {numbers: [-1, 5, 6, -2, 20, -50, 4], sum: 29},
      {numbers: [1, 100, -50, -50, 100, 1], sum: 102},
      {numbers: [-50, -50, 100, 2], sum: 102},
      {numbers: [-3, -5, -10, -2, -7], sum: -2},
      {numbers: [0, 0, 0], sum: 0},
      {numbers: [-1, -1, -1, 0, -1, -1], sum: 0}
  ].each do |input|
    it "#{input[:sum]} should be max sum of #{input[:numbers].inspect}" do
      calculator = MaxConsecutiveSumCalculator.new(input[:numbers], true)
      result = calculator.result
      puts result.inspect
      result[:sum].should == input[:sum]

      recursive_result = RecursiveMaxConsecutiveSumCalculator.new(input[:numbers])
      recursive_result.result[:sum].should == input[:sum]
    end

    [nil,[]].each do |bad_input|
      it "should raise error on #{bad_input.inspect}" do
        expect {
          RecursiveMaxConsecutiveSumCalculator.new(bad_input)
        }.to raise_error

        expect {
          MaxConsecutiveSumCalculator.new(bad_input)
        }.to raise_error
      end
    end

  end

end

recursive_max_consecutive_sum_calculator.rb

class RecursiveMaxConsecutiveSumCalculator
  attr_reader :result

  def initialize(numbers)
    raise "Input array shouldn't be nil or empty" if numbers.nil? || numbers.empty?

    @result = {}
    @result[:sum] = calculate_sum(numbers)
  end

  private

  def calculate_sum(numbers)
    return numbers.first if numbers.size == 1

    if numbers[0] <= numbers[-1]
      numbers[1] += numbers[0] if numbers[0] > 0
      calculate_sum(numbers[1..-1])
    else
      numbers[-2] += numbers[-1] if numbers[-1] > 0
      calculate_sum(numbers[0..-2])
    end
  end

end