Largest divisible subset optimization
Yes, the running time is \$O(n^2)\$.

When writing ruby, it's best to take advantage of ruby's built in methods, rather than writing procedural code the same way you would in C or Java.

Also, this problem expresses itself more naturally with recursion. 

Notes on the solution below:


nums, in this recursion, are "the remaining numbers to be processed".  We start with smallest (first number on sorted list), pop off the head on each iteration.
ret is a hash of the results for all smaller numbers -- the same is max_result in the OP.


Here's a possible rewrite:

def largest_divisible_subset(nums, ret={})
  return ret.values.max_by(&amp;:size) || [] if nums.empty?
  nums = nums.sort if ret.empty?
  head, *tail = nums
  max_set = ret.select {|n| head % n == 0}.values.max_by(&amp;:size) || []
  ret[head] = max_set.dup.push(head)
  largest_divisible_subset(tail, ret)
end