Daily LeetCode 368. Largest Divisible Subset

https://leetcode.com/problems/largest-divisible-subset/

Medium

问题描述

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)

Example 2:

Input: [1,2,4,8]
Output: [1,2,4,8]

思路及代码

这一题有点类似于求最长升序子串，需要从一系列数字中找出最长的子串，要求这个子串中每一对数字都是能够整除的，即一个数为另一个数的约数。

既然与LIS类似，就可以用动态规划来解题，维护一个一维数组dp，dp[i]保存的是一个列表，表示从0~i位置满足题目要求的最长子串。

通过一个二重循环更新dp数组，先将题目给定数组从小到大排序，i从0向后遍历，j从i位置向前遍历，第二重遍历的目的是寻找能够被nums[i]整除的nums[j]，同时比较dp[i]和dp[j]对应的子串的大小，因为我们要找最长子串，因此只在len(dp[j])>max_size的情况下才对其进行更新。

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if len(nums) == 0: return []

        dp = [[] for _ in range(len(nums))]
        max_index, max_size = 0, -1
        final_index, final_size = 0, -1
        nums.sort()

        for i in range(len(nums)):
            for j in range(i, -1, -1):
                if nums[i] % nums[j] == 0 and len(dp[j]) > max_size:
                    max_index = j
                    max_size = len(dp[j])
            if max_size != -1:
                dp[i] += dp[max_index]
            dp[i].append(nums[i])

            if len(dp[i]) > final_size:
                final_size = len(dp[i])
                final_index = i
            max_index, max_size = 0, -1

        return dp[final_index]