leetcode Largest Divisible Subset

leetcode Largest Divisible Subset

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:
1
2
3
nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)
Example 2:
1
2
3
nums: [1,2,4,8]

Result: [1,2,4,8]

题目地址：leetcode Largest Divisible Subset

题意：给定一个数组，求其中的一个最大子集，要求该子集中任意的两个元素满足 x % y ==0 或者 y % x==0

思路：其实和求最大上升子序列LIS差不多，只不过这题要求输出序列而已。

先把数组排好序。首先要明确，若a<b且b%a==0 , b <c 且 c%b==0那么必然有c%a==0

我们设dp[i] 为最大的子集长度，更新的时候保存上一个的下标即可。

C++

class Solution {
public:
	vector<int> largestDivisibleSubset(vector<int>& nums) {
		vector<int> ans;
		if (nums.empty()) return ans;
		sort(nums.begin(), nums.end());
		int n = nums.size();
		vector<int> dp(n, 1), index(n, -1);
		int max_index=0, max_dp=1;
		for (int i = 0; i < n; i++) {
			for (int j = i - 1; j >=0 ; j--) {
				if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
					dp[i] = dp[j] + 1;
					index[i] = j;
				}
			}
			if (max_dp < dp[i]) {
				max_dp = dp[i];
				max_index = i;
			}
		}
		for (int i = max_index; i != -1; i = index[i])
			ans.push_back(nums[i]);
		return ans;
	}
};

Java

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> ans = new ArrayList<Integer>();
        if (nums.length == 0) return ans;
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n], index = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(index, -1);
        int max_index = 0, max_dp = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i - 1 ; j >= 0 ; j--) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    index[i] = j;
                }
            }
            if (max_dp < dp[i]) {
                max_dp = dp[i];
                max_index = i;
            }
        }
        for (int i = max_index; i != -1; i = index[i])
            ans.add(nums[i]);
        return ans;
    }
}

Python

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums: return []
        nums.sort()
        n = len(nums)
        dp, index = [1] * n, [-1] * n
        max_dp, max_index = 1, 0
        for i in xrange(n):
            for j in xrange(i-1,-1,-1):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    index[i] = j

            if max_dp < dp[i]:
                max_dp, max_index = dp[i], i

        ans = []
        while max_index != -1:
            ans.append(nums[max_index])
            max_index = index[max_index]
        return ans

本题是leetcode 368 Largest Divisible Subset 题解

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/