Largest divisible subset optimization So this is my solution to the following leetcode problem: https://leetcode.com/problems/largest-divisible-subset/description/

How could I optimize this code?
I think the run time is \$\mathcal{O}(n^2)\$, is that correct?

def largest_divisible_subset(nums)
return nums if nums.length &lt; 2
nums.sort!
max_result = {}
(0).upto(nums.length - 1) do |i|
    j = i - 1
    result = Set.new


    while j &gt;= 0
       if nums[i] % nums[j] == 0
          if max_result[nums[j]] &amp;&amp; max_result[nums[j]].length &gt; result.length
             result =  max_result[nums[j]].dup
          elsif result.length == 0
             result.add(nums[j])
          end
       end

        j -= 1
        break if result.length &gt; nums[0..j].length
    end

    result.add(nums[i])
    max_result[nums[i]] = result
end

   max_result.values.max{|a,b| a.length &lt;=&gt; b.length }.to_a
end
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