368

368. Largest Divisible Subset (Medium)

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 solutions, return any of them.

 

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

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

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2 * 109
• All the integers in nums are unique.

Companies:
Codenation, Google, Microsoft, Apple

Related Topics:
Array, Math, Dynamic Programming, Sorting

Solution 1. DP

Sort the array in ascending order.

Let dp[i] be the size of the largest divisible subset that is within A[0..i] and contain A[i].

dp[i] = max(dp[j] + 1 | 0 <= j < i && A[i] % A[j] == 0)
dp[0] = 1

In order to recover the subset, we also use a prev array where prev[i] is the choice of previous index corresponding to dp[i].

// OJ: https://leetcode.com/problems/largest-divisible-subset/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& A) {
        sort(begin(A), end(A));
        int N = A.size(), last = 0;
        vector<int> dp(N, 1), prev(N, -1), ans;
        for (int i = 1; i < N; ++i) {
            for (int j = 0; j < i; ++j) {
                if (A[i] % A[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[last]) last = i;
        }
        for (int i = last; i != -1; i = prev[i]) ans.push_back(A[i]);
        return ans;
    }
};