Largest Divisible Subset
这个博客的文章讲的不错~ 重点比我说的好。https://segmentfault.com/a/1190000005922634
把这题放在 LIS 分类下面,主要是因为长的和 LIS 的 O(n^2) DP 解法很像。
这题正确性的保证:对于排序数组 nums 的两个 index,i, j 并且 j < i 的情况下,如果 nums[i] % nums[j] == 0,那么包含 nums[j] 的 subset 里所有元素也一定能整除 nums[i]. 因为 nums[j] 是其 subset 中当前最大的元素,而且一定可以整除所有比它小的。
主要不同点:
因为最后要输出结果,得存个 parent 数组记录每个序列的前一个元素
每次往回扫的时候,不能像 LIS 那样看到大的就停手,要走到底
这么讲的话,貌似要输出具体 LIS 序列的题,也可以这么做。。O(n^2) 时间,O(n) 空间就可以了。
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> rst = new ArrayList<>();
if(nums == null || nums.length == 0) return rst;
Arrays.sort(nums);
int[] dp = new int[nums.length];
int[] parent = new int[nums.length];
Arrays.fill(dp, 1);
Arrays.fill(parent, -1);
int maxIndex = -1;
int maxLen = 1;
for(int i = 0; i < nums.length; i++){
for(int j = i - 1; j >= 0; j--){
if(nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1){
dp[i] = dp[j] + 1;
parent[i] = j;
if(dp[i] > maxLen){
maxLen = dp[i];
maxIndex = i;
}
}
}
}
if(maxIndex == -1){
rst.add(nums[0]);
} else {
while(maxIndex != -1){
rst.add(nums[maxIndex]);
maxIndex = parent[maxIndex];
}
}
return rst;
}
}
Last updated
Was this helpful?