Max SubArray

max_subarray.rb

#######################
# Version 1 - O(n^2)
#######################

def max_seq(chars, x = 0, y = 0)
  return chars if chars.size < 2

  combinations = {}

  (0...chars.size).each do |x|
    sum = 0
    (x..chars.size-1).each do |y|
      sum += chars[y]
      #puts "#{x}, #{y} = #{sum}".ljust(12) + "   comb: #{combinations[chars[x-1..y]] - chars[x-1]} y: #{chars[y]}" if x > 0
      sum = combinations[chars[x-1..y]] - chars[x-1] if x > 0
      combinations[chars[x..y]] = sum
    end
  end

  #p combinations
  combinations.max_by { |k,v| v }[1]
end

p max_seq [2,3,4,-12,5,6]

#######################
# Version 2 - O(n^2)
#######################

def max_seq(chars, x = 0, y = 0)
  combinations = {}

  (0...chars.size).each do |x|
    sum = 0
    (x..chars.size-1).each do |y|
      sum += chars[y]
      combinations[sum] = chars[x..y]
    end
  end

  combinations.max_by { |k,v| k }[1]
end

#######################
# Version 3 - O(n^2) - Array
#######################

def max_seq(chars, x = 0, y = 0)
return chars if chars.size < 2

  combinations = Array.new(chars.size) { [] }
  max = -9999
  sum = 0

  (0...chars.size).each do |x|
    (x..chars.size-1).each do |y|
      sum += chars[y] if x == 0
      sum = combinations[x-1][y] - chars[x-1] if x > 0
      combinations[x][y] = sum
      max = sum if sum > max
    end
  end
  max
end