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:

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

Example 2:

nums: [1,2,4,8]
Result: [1,2,4,8]

DP

复杂度

O(N^2) 时间 O(N) 空间

思路

和LIS很相似，dp[i]表示nums数组从0到i的最大集合的size.
这题应该分成两个问题：

1. 得到最大集合size

2. 输出这个集合

对于第一个问题，最大集合size就是dp数组的最大值，可以边画表边维护一个当前最大值;
对于第二个问题，我们要维护一个parent数组，记录nums[i]加入到了哪个集合;
dp[i] = max(dp[i], dp[j] + 1), where 0 3，于是更新dp[i]
注意就是不能停，找到一个能整除并不够，前面有可能有更大的啊~~

代码

主程序：

public class Solution {
public List largestDivisibleSubset(int[] nums) {
if (nums.length == 0)
return new ArrayList();
//nums has at least one element
int n = nums.length;
Arrays.sort(nums);
int[] dp = new int[n];
Arrays.fill(dp, 1);
int[] parent = new int[n];
Arrays.fill(parent, -1);//当parent数组中某数为-1时，表示这个数自己是一个集合
int max = 1, max_index = -1;
for (int i = 1; i = 0; j--) { //i > j
if (nums[i] % nums[j] == 0 && dp[i] max) {
max = dp[i];
max_index = i;
}
}
}
}
return genResult(nums, parent, max_index);
}
}
Utility:

public List genResult(int[] nums, int[] parent, int max_index) {
List result = new ArrayList();
if (max_index == -1) { //每个数都是单独成集合，都不能合并
result.add(nums[0]); //随便输出一个数，这里选第一个
return result;
}
int iter = max_index;
while (iter != -1) {
result.add(nums[iter]);
iter = parent[iter];
}
return result;
}

关键字：leetcode, nums, int, parent

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！