描述

給一個(gè)由 無(wú)重復(fù)的正整數(shù) 組成的集合，找出滿足任意兩個(gè)元素 (Si, Sj) 都有 Si % Sj = 0 或 Sj % Si = 0 成立的最大子集

如果有多種解集，返回其中任意一個(gè)。

樣例

給一個(gè)數(shù)組 [1,2,3]，返回 [1,2] 或 [1,3]
給一個(gè)數(shù)組 [1,2,4,8]，返回 [1,2,4,8]

代碼

class Solution:
    """
    @param: nums: a set of distinct positive integers
    @return: the largest subset 
    """
    def largestDivisibleSubset(self, nums):
        # write your code here
        nums.sort()
        n = len(nums)
        dp = [1 for i in range(n)]
        dp_index = [-1 for i in range(n)]
        for i in range(1, n):
            max_sum = 0
            for j in range(0, i):
                if nums[i]%nums[j] == 0 and dp[j] > max_sum:
                    max_sum = dp[j]
                    dp_index[i] = j
            dp[i] += max_sum
        sta = 0
        maxL = 0
        for key, val in enumerate(dp):
            if val > maxL:
                maxL = val
                sta = key
        result = []
        while sta>=0:
            result.append(nums[sta])
            sta = dp_index[sta]
        return result
            

思路

思路比較簡(jiǎn)易，就是最長(zhǎng)上升子序列，只不過之前的大小比較條件變化為了整除。但是值得注意的是，它要返回的不是最大整除序列的長(zhǎng)度，而是序列數(shù)組，所以需要記錄。兩種思路，一種是用二維數(shù)據(jù)dp[i][j]直接把數(shù)組記錄下來(lái)，dp[i]里存最大的那個(gè)數(shù)組，感覺比較麻煩，第二種就比較簡(jiǎn)單，因?yàn)樾蛄兄g是有連接關(guān)系的，所有用dp_index[i]數(shù)組來(lái)存下標(biāo)，dp_index[i]就代表當(dāng)前數(shù)之前的最大整除數(shù)序列的最后一個(gè)數(shù)的下標(biāo)，這樣最后在dp[i]中最大的那個(gè)數(shù)的下標(biāo)就是遍歷dp_index[i]下標(biāo)的起始位置。最后把遍歷的下標(biāo)對(duì)應(yīng)的數(shù)返回就好。

題目來(lái)源

https://www.lintcode.com/problem/largest-divisible-subset/description