Python O(N^2) solution


  • 0
    N
    class Solution(object):
    
    def largestDivisibleSubset(self, nums):
        if not nums:
            return []
        
        l = len(nums)
        counts = [1] * l
        pre_indexs = [-1] * l
        max_length, max_index = 0, -1
        nums.sort()
        
        for index, value in enumerate(nums):
            for prev_index in xrange(index):
                if value % nums[prev_index] == 0:
                    if counts[prev_index] + 1 > counts[index]:
                        counts[index] = counts[prev_index] + 1
                        pre_indexs[index] = prev_index
            if counts[index] > max_length:
                max_length = counts[index]
                max_index = index
        
        result = []
        while max_index > -1:
            result.append(nums[max_index])
            max_index = pre_indexs[max_index]
        return result

Log in to reply
 

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