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) 空间就可以了。
Last updated