# Python dp n^2 solution

• We first do some math work. For two numbers, A and B, if A < B, A % B must > 0 (A != 0). The only chance A % B == 0 must be A >= B.

With this idea, we sort the list. Then, the question turns similar to no.300 longest increasing subsequence. For ith number, its largest divisible subset is the max of subset of any j from 0 - i-1 in which nums[i] % nums[j] == 0.

``````class Solution(object):
def largestDivisibleSubset(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
from copy import copy
nums.sort()
n = len(nums)
if n == 0: return []
dp = [0] * n
dp[0] = [nums[0]]
#print(dp)
for i in xrange(1, n):
curNum = nums[i]
maxSet = []
for j in xrange(i):
if curNum % nums[j] == 0:
localSet = copy(dp[j])
if len(localSet) > len(maxSet):
maxSet = localSet

maxSet.append(nums[i])
dp[i] = maxSet
#print(dp)

#print(dp)
res = []
for localSet in dp:
if len(localSet) > len(res):
res = localSet
return res``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.