Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:
	answer[i] % answer[j] == 0, or
	answer[j] % answer[i] == 0
If there are multiple sequences with the largest size, return any of them.
Example 1:
Input:
n = 3
arr = [1,2,3]
Output:
[1,2]
Explanation:
Largest Divisble Subset is [1,2].
Example 2:
Input:
n = 4
arr = [1,2,4,8]
Output:
[1,2,4,8]
Your Task:
You don't have to read input or print anything. Your task is to complete the function LargestSubset() which takes the integer n and array arr and returns the Largest Divisible Subset.
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(n^{2})
Constraint:
1 <= n <= 1000
1  <= arr[i] <= 2 * 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def LargestSubset(self, n, arr):

        #Code here

Solutions:
class Solution:

	def LargestSubset(self, n, arr):
		arr.sort()
		dp = [1] * n
		p = [-1] * n
		val = 0
		pos = 0
		for i in range(1, n):
			for j in range(i):
				if arr[i] % arr[j] == 0 and dp[i] < dp[j] + 1:
					dp[i] = dp[j] + 1
					p[i] = j
			if val < dp[i]:
				val = dp[i]
				pos = i
		ans = []
		while pos != -1:
			ans.append(arr[pos])
			pos = p[pos]
		return ans


class Solution:

	def LargestSubset(self, n, arr):
		arr.sort()
		dp = [1 for i in range(n)]
		Max = 1
		for i in range(1, n):
			for j in range(i):
				if arr[i] % arr[j] == 0 and 1 + dp[j] > dp[i]:
					dp[i] = 1 + dp[j]
					if Max < dp[i]:
						Max = dp[i]
		prev = -1
		ans = []
		for i in range(n - 1, -1, -1):
			if dp[i] == Max:
				if prev % arr[i] == 0 or prev == -1:
					ans.append(arr[i])
					prev = arr[i]
					Max -= 1
		return ans


class Solution:

	def LargestSubset(self, n, arr):
		arr.sort()
		dp = []
		hash = []
		for i in range(n):
			dp.append(1)
			hash.append(i)
		dp[0] = 1
		for i in range(1, n):
			for j in range(i - 1, -1, -1):
				if arr[i] % arr[j] == 0 and 1 + dp[j] > dp[i]:
					hash[i] = j
					dp[i] = dp[j] + 1
		maxi = -2
		l = -1
		for i in range(n):
			if dp[i] > maxi:
				maxi = dp[i]
				l = i
		ans = []
		while hash[l] != l:
			ans.append(arr[l])
			l = hash[l]
		ans.append(arr[l])
		return ans[::-1]


class Solution:

	def LargestSubset(self, n, arr):
		dp = [1 for i in range(n)]
		res = [i for i in range(n)]
		arr.sort()
		for i in range(n):
			for j in range(i):
				if arr[i] % arr[j] == 0 and 1 + dp[j] > dp[i]:
					dp[i] = 1 + dp[j]
					res[i] = j
		count = -1
		indx = -1
		for k in range(n):
			if dp[k] > count:
				count = dp[k]
				indx = k
		ans = []
		ans.append(arr[indx])
		while res[indx] != indx:
			indx = res[indx]
			ans.append(arr[indx])
		return ans


class Solution:

	def LargestSubset(self, n, arr):
		if len(arr) == 1:
			return arr
		dp = {}
		prev = {}
		arr.sort()
		for i in range(n):
			dp[i] = 1
			prev[i] = -1
		answer = 0
		answerIndex = -1
		for i in range(1, n):
			maxi = dp[i]
			prevI = prev[i]
			for j in range(i):
				if not arr[i] % arr[j]:
					curr = 1 + dp[j]
					if curr > maxi:
						maxi = curr
						prevI = j
			dp[i] = maxi
			prev[i] = prevI
			if dp[i] > answer:
				answer = dp[i]
				answerIndex = i
		lds = []
		while answerIndex != -1:
			lds.insert(0, arr[answerIndex])
			answerIndex = prev[answerIndex]
		return lds


class Solution:

	def LargestSubset(self, n, a):
		h = [i for i in range(n)]
		dp = [1] * n
		ma = 1
		li = 0
		a.sort()
		for i in range(1, n):
			h[i] = i
			for pre in range(i):
				if a[i] % a[pre] == 0 and dp[i] < 1 + dp[pre]:
					dp[i] = 1 + dp[pre]
					h[i] = pre
			if ma < dp[i]:
				ma = dp[i]
				li = i
		ans = []
		ans.append(a[li])
		while h[li] != li:
			li = h[li]
			ans.append(a[li])
		return ans


class Solution:

	def LargestSubset(self, n, arr):
		arr.sort()
		dp = [1] * n
		hash = [1] * n
		last_idx = 0
		maxi = 1
		for idx in range(n):
			hash[idx] = idx
			for prev in range(idx):
				if arr[idx] % arr[prev] == 0 and 1 + dp[prev] > dp[idx]:
					dp[idx] = 1 + dp[prev]
					hash[idx] = prev
			if dp[idx] > maxi:
				maxi = dp[idx]
				last_idx = idx
		temp = []
		temp.append(arr[last_idx])
		while hash[last_idx] != last_idx:
			last_idx = hash[last_idx]
			temp.append(arr[last_idx])
		return temp


class Solution:

	def LargestSubset(self, n, arr):
		arr.sort()
		dp = [1 for i in range(n)]
		bt = [i for i in range(n)]
		for i in range(n):
			for j in range(i):
				if arr[i] % arr[j] == 0 and dp[i] <= dp[j]:
					dp[i] = dp[j] + 1
					bt[i] = j
		last = 0
		maxi = float('-inf')
		for i in range(n):
			if dp[i] > maxi:
				maxi = dp[i]
				last = i
		ans = []
		while last != bt[last]:
			ans.append(arr[last])
			last = bt[last]
		ans.append(arr[last])
		return ans


class Solution:

	def LargestSubset(self, n, arr):
		ind = [i for i in range(n)]
		dp = [1 for i in range(n)]
		arr.sort()
		for i in range(n):
			for j in range(i):
				if arr[i] % arr[j] == 0 or arr[j] % arr[i] == 0:
					if dp[j] + 1 > dp[i]:
						dp[i] = dp[j] + 1
						ind[i] = j
		maxi = 0
		maxii = 0
		for i in range(n):
			if maxi < dp[i]:
				maxi = dp[i]
				maxii = i
		l = [arr[maxii]]
		while maxii != ind[maxii]:
			maxii = ind[maxii]
			l.append(arr[maxii])
		return l


class Solution:

	def LargestSubset(self, n, arr):
		arr.sort()
		dp = []
		hash = []
		for i in range(n):
			dp.append(1)
			hash.append(i)
		maxi = 1
		li = 0
		for i in range(n):
			for prev in range(i):
				if (arr[i] % arr[prev] == 0 or arr[prev] % arr[i] == 0) and 1 + dp[prev] > dp[i]:
					dp[i] = 1 + dp[prev]
					hash[i] = prev
			if dp[i] > maxi:
				maxi = dp[i]
				li = i
		ans = [arr[li]]
		while li != hash[li]:
			ans.append(arr[hash[li]])
			li = hash[li]
		return ans


class Solution:

	def LargestSubset(self, n, nums):
		nums.sort()
		dp = [[n] for n in nums]
		for i in range(1, n):
			for j in range(i):
				if nums[i] % nums[j] == 0 and len(dp[i]) < len(dp[j]) + 1:
					dp[i] = dp[j] + [nums[i]]
		res = []
		for r in dp:
			if len(res) < len(r):
				res = r
		return res


class Solution:

	def LargestSubset(self, n, nums):
		nums.sort()
		n = len(nums)
		maxi = 1
		dp = [1] * n
		lastidx = 0
		has = [None] * n
		for idx in range(n):
			has[idx] = idx
			for prev_idx in range(idx):
				if nums[idx] % nums[prev_idx] == 0 and 1 + dp[prev_idx] > dp[idx]:
					dp[idx] = 1 + dp[prev_idx]
					has[idx] = prev_idx
			if dp[idx] > maxi:
				maxi = dp[idx]
				lastidx = idx
		temp = []
		temp.append(nums[lastidx])
		while has[lastidx] != lastidx:
			lastidx = has[lastidx]
			temp.append(nums[lastidx])
		temp.reverse()
		return temp


class Solution:

	def LargestSubset(self, n, arr):
		dp = [1 for i in range(n)]
		has = [1 for i in range(n)]
		arr.sort()
		maxi = 0
		last = 0
		for i in range(n):
			has[i] = i
			for j in range(i):
				if arr[i] % arr[j] == 0 and dp[i] < dp[j] + 1:
					dp[i] = dp[j] + 1
					has[i] = j
			if maxi < dp[i]:
				maxi = dp[i]
				last = i
		temp = []
		temp.append(arr[last])
		while last != has[last]:
			last = has[last]
			temp.append(arr[last])
		return temp


class Solution:

	def LargestSubset(self, n, arr):
		arr.sort()
		prev = [i for i in range(0, n)]
		lds = [1] * n
		endidx = 0
		maxlen = 0
		for i in range(1, n):
			for j in range(0, i):
				if arr[i] % arr[j] == 0 and lds[i] <= lds[j]:
					lds[i] = 1 + lds[j]
					prev[i] = j
			if lds[i] > maxlen:
				maxlen = lds[i]
				endidx = i
		ans = []
		idx = endidx
		ans.append(arr[idx])
		while prev[idx] != idx:
			idx = prev[idx]
			ans.append(arr[idx])
		return ans


class Solution:

	def LargestSubset(self, n, nums):
		nums.sort()
		dp = [1] * n
		backtrack = [i for i in range(n)]
		lis = dp[0]
		lastIndex = 0
		for ind in range(1, n):
			for prev in range(ind):
				if nums[ind] % nums[prev] == 0 and dp[ind] < dp[prev] + 1:
					dp[ind] = dp[prev] + 1
					backtrack[ind] = prev
			if dp[ind] > lis:
				lis = dp[ind]
				lastIndex = ind
		ans = [0] * lis
		ans[0] = arr[lastIndex]
		ind = 1
		while backtrack[lastIndex] != lastIndex:
			lastIndex = backtrack[lastIndex]
			ans[ind] = arr[lastIndex]
			ind += 1
		return ans[::-1]


class Solution:

	def LargestSubset(self, n, arr):
		n = len(arr)
		dp = [1] * n
		hash = [i for i in range(n)]
		lastIndex = 0
		maxi = 1
		arr.sort()
		for i in range(n):
			for prev in range(i):
				if arr[i] % arr[prev] == 0 and 1 + dp[prev] > dp[i]:
					dp[i] = 1 + dp[prev]
					hash[i] = prev
			if dp[i] > maxi:
				maxi = dp[i]
				lastIndex = i
		temp = []
		temp.append(arr[lastIndex])
		while hash[lastIndex] != lastIndex:
			lastIndex = hash[lastIndex]
			temp.append(arr[lastIndex])
		return temp[::-1]


class Solution:

	def LargestSubset(self, n, l1):
		l1.sort()
		dp = [1 for i in range(n)]
		hsh = [i for i in range(n)]
		mxLen = 0
		mxLenIdx = 0
		for i in range(1, n):
			for j in range(0, i):
				if l1[i] % l1[j] == 0:
					if dp[j] + 1 > dp[i]:
						dp[i] = dp[j] + 1
						hsh[i] = j
			if dp[i] > mxLen:
				mxLen = dp[i]
				mxLenIdx = i
		tmp = []
		lstIdx = mxLenIdx
		tmp.append(l1[mxLenIdx])
		while lstIdx != hsh[lstIdx]:
			lstIdx = hsh[lstIdx]
			tmp.append(l1[lstIdx])
		return tmp


class Solution:

	def LargestSubset(self, n, arr):
		arr.sort()
		dp = [1 for _ in range(n)]
		ha = [0 for _ in range(n)]
		maxi = 1
		last = 0
		for i in range(n):
			ha[i] = i
			for j in range(i):
				if (arr[j] % arr[i] == 0 or arr[i] % arr[j] == 0) and dp[j] + 1 > dp[i]:
					dp[i] = dp[j] + 1
					ha[i] = j
			if dp[i] > maxi:
				maxi = dp[i]
				last = i
		ans = []
		ans.append(arr[last])
		while ha[last] != last:
			last = ha[last]
			ans.append(arr[last])
		return ans[::-1]


class Solution:

	def LargestSubset(self, n, nums):
		arr.sort()
		dp = [0] * n
		hash = [0] * n
		for i in range(0, n):
			hash[i] = i
			for j in range(0, i):
				if arr[i] % arr[j] == 0 and 1 + dp[j] > dp[i]:
					dp[i] = 1 + dp[j]
					hash[i] = j
		ans = -1
		lastIndex = -1
		for i in range(0, n):
			if dp[i] > ans:
				ans = dp[i]
				lastIndex = i
		temp = []
		temp.append(arr[lastIndex])
		while hash[lastIndex] != lastIndex:
			lastIndex = hash[lastIndex]
			temp.append(arr[lastIndex])
		temp.reverse()
		return temp


class Solution:

	def LargestSubset(self, n, nums):
		n = len(nums)
		dp = [1 for i in range(n)]
		hashing = [0 for i in range(n)]
		lastInd = 0
		maxi = 1
		nums.sort()
		for i in range(0, n):
			hashing[i] = i
			for prev in range(0, i):
				if nums[i] % nums[prev] == 0 and dp[i] < 1 + dp[prev]:
					dp[i] = 1 + dp[prev]
					hashing[i] = prev
			if dp[i] > maxi:
				maxi = dp[i]
				lastInd = i
		temp = []
		temp.append(nums[lastInd])
		while hashing[lastInd] != lastInd:
			lastInd = hashing[lastInd]
			temp.append(nums[lastInd])
		return temp[::-1]


class Solution:

	def LargestSubset(self, n, nums):
		nums.sort()
		output = [[x] for x in nums]
		for i in range(len(nums)):
			for j in range(i):
				if nums[i] % nums[j] == 0 and len(output[i]) < len(output[j]) + 1:
					output[i] = output[j] + [nums[i]]
		return max(output, key=lambda x: len(x))