[Python] Short DP with O(n^2) explained (update)
First of all, notice, that if we need to find 3 numbers  given properties, than if we put then in decreasing order a > b > c, than it is sufficient and enough t
First of all, notice, that if we need to find `3` numbers  given properties, than if we put then in decreasing order `a > b > c`, than it is sufficient and enough that `a%b = 0` and `b%c=0`, then it is automatically `a%c=0`. \n\nLet us now sort our numbers and in `sol[i]` list keep the best solution, where the biggest number is equal to `nums[i]`. How can we find it? Look at all smaller numbers and if `nums[i]` is divisible by this smaller number, we can update solution. Let us go through example: `nums = [4,5,8,12,16,20].`\n1. `sol[0] = [4]`, the biggest divisible subset has size `1`.\n2. `sol[1] = [5]`, because `5 % 4 != 0`.\n3. `sol[2] = [4,8]`, because `8 % 4 = 0`.\n4. `sol[3] = [4,12]`, because `12 % 4 = 0`. \n5. `sol[4] = [4,8,16]`, because `16 % 8 = 0` and `16 % 4 = 0` and we choose `8`, because it has longer set.\n6. `sol[5] = [4,20]` (or `[5,20]` in fact, but it does not matter). We take `[4,20]`, because it has the biggest length and when we see `5`, we do not update it.\n7. Finally, answer is `[4,8,16]`.\n\n\n**Complexity**: time complexity is `O(n^2)`, because we fist sort our numbers and then we have double loop. Space complexity also potentially `O(n^2)`, but for big `n`, length of the longest subset will not be more than `32`: (each time you new number will be at least twice bigger than previous, so there will be maximum 32 numbers in our set) so so we can say it is `O(32n)`.\n\n### Possible improvements\nNote similarity of this problem with problem **300 Longest Increasing Subsequence**, however it is different, and we can not apply `O(n log n)` algorighm here directly, when we add new number we can not use binary search.\nThere is idea by **@yanrucheng** with comlexity `O(nlogn + n*sqrt(V))`, where `V` is the biggest number. I am interested, if there is `O(n log n)` solution here? If you know such method please let me know!\n\n\n```\nclass Solution:\n    def largestDivisibleSubset(self, nums):\n        if len(nums) == 0: return []\n        nums.sort()\n        sol = [[num] for num in nums]\n        for i in range(len(nums)):\n            for j in range(i):\n                if nums[i] % nums[j] == 0 and len(sol[i]) < len(sol[j]) + 1:\n                    sol[i] = sol[j] + [nums[i]]\n        return max(sol, key=len)\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming']